完全背包问题
完全背包问题是 0-1 背包问题的衍生问题。
区别
完全背包中每个物品可以重复选择（选择后仍然存在），与 0-1 背包中每个物品只能选一次不同。
状态转移方程
在完全背包问题中，选择该物品的转移方程改为：
dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i])
注意这里第二项是 dp[i][…] 而非 dp[i-1][…]，因为物品 i 可以重复选择。j 需要从小到大遍历。
核心思想
允许重复选择意味着在决定是否选择物品 i 时，选择物品 i 之后仍然可以继续选择物品 i，因此在同一行内传递状态。
链接到
- 上一个知识点：2.5 0-1背包问题
- 下一个知识点：2.7 分组背包问题