定义一个二维数组 dp 存储最大价值,其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。
设第 i 件物品体积为 w,价值为 v,根据第 i 件物品是否添加到背包中,可以分两种情况讨论:
第 i 件物品没添加到背包,总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值,
dp[i][j] = dp[i-1][j]。
第 i 件物品添加到背包中,
dp[i][j] = dp[i-1][j-w] + v。
第 i 件物品可添加也可以不添加,取决于哪种情况下最大价值更大。因此,0-1 背包的状态转移方程为:
dp[i][j]=max(dp[i-1][]j),dp[i-1][j-w]+v)
空间优化
在程序实现时可以对 0-1 背包做优化。观察状态转移方程可以知道,前 i 件物品的状态仅与前 i-1 件物
品的状态有关,因此可以将 dp 定义为一维数组,其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。此时,
dp[i]=maz(dp[i], dp[j-w] +v)
原版
0-1背包即数组中的元素不可重复使用,nums放在外循环,target在内循环,且内循环倒序;```language
for (int num : nums) {
for (int i = target; i >=0; i--) {
}
}
变种
完全背包:物品数量为无限个。即数组中的元素可重复使用,nums放在外循环,target在内循环。且内循环正序。
for (int num : nums) {
for (int i = num ; i <=target ; i++) {
}
}
多重背包:物品数量有限制
多维费用背包:物品不仅有重量,还有体积,同时考虑这两种限制
其它:物品之间相互约束或者依赖 如果组合问题需考虑元素之间的顺序,需将target放在外循环,将nums放在内循环。
```language
for (int i = 1; i <=target; i++) {
for (int num : nums) {
}
}
组合问题公式
dp[i] += dp[i-num]
True、False问题公式
dp[i] = dp[i] or dp[i-num]
最大最小问题公式
dp[i] = min(dp[i], dp[i-num]+1)或者dp[i] = max(dp[i], dp[i-num]+1)
规律
背包问题 总是输入一个数组/列表,与一个目标值
dp的长度一般为target+1,具体情况不同
往往dp[0]需要被赋值
return一般是dp[target]
能给我打赏么?总结不易!