01 背包

本篇对应源码见仓库 solutions/xcpc/algorithm/dp/knapsack-01/。

问题分析

• 给定背包最大容量 V, n 件物品，每件物品有重量（体积）w, 价值 v，每件物品最多选一次，求背包能装下物品的最大总价值。
• 对每件物品考虑选或者不选，选还需要考虑背包能不能装下。

状态定义

• 使用滚动数组（一维）
• $dp[j]$ 背包容量为 $j$ 时能装的最大价值

遍历方式

• 二重循环
• 第一层枚举物品（$for\ i\ in\ 1..n$)
• 第二层逆序枚举背包容量($for \ j \ in\ W..w[i]$)

状态转移方程

dp[j] = max(dp[j], dp[j - w[i] + v[j]

拓展问题

请注意对不同问题的 $dp$ 数组的定义，初始化，状态转移方程的异同。

求可行性（恰好装满）

• 状态定义： $dp[j]$ 为容量为 $j$ 的背包能否装满
• 初始化： dp[0] = true, dp[1..n] = false
• 状态转移： dp[j] = dp[j] | dp[j - w[i]]

求方案数(恰好装满)

• 状态定义： $dp[j]$ 为容量为 $j$ 的背包能够装满的方案总数
• 初始化： dp[0] = 1, dp[1..n] = 0
• 状态转移: dp[j] = dp[j] + dp[j - w[i]]

求最大价值

• 状态定义：$dp[j]$ 为容量为 $j$ 的背包能装下的最大价值
• 初始化： dp[0..n] = 0(不要求恰好装满), dp[0] = 0, dp[1..n] = -inf(要求恰好装满)
• 状态转移： dp[j] = max(dp[j], dp[j - w[i]] + v[i](不要求恰好装满), if(dp[j - w[i]] != -inf) dp[j] = max(dp[j], dp[j - w[i]] + v[i]