背包专题(考研自用)

• w[i]表示第i个物品的价值
• v[i]表示第i个物品的体积

01背包

转移方程

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

滚动优化

注意到转移仅仅依赖于上一次的结果，因此可以省去物品那一维
dp[j] = max(dp[j], dp[j - v[i]] + w[i]) i = 1,2,...n
这里枚举j时需要注意从大到小枚举，若从小到大枚举，则转移方程获取的是 i层的结果，因此要从大到小枚举

完全背包

观察dp[i][j]和dp[i][j - v[i]]可得如下的转移方程
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])

滚动优化

注意到转移仅仅依赖于上一次和当前层的结果，因此可以省去物品那一维
dp[j] = max(dp[j], dp[j - v[i]] + w[i]) i = 1,2,...n
这里枚举j时需要注意从小到到枚举，因为转移方程依赖于 i层的结果