背包
2026-08-28 18:02:09
发布于:上海
01背包:有 n 件物品和一个容量为 v 的背包。第 i 件物品体积为 wi,价值为 vi,每件物品只有一件,只能选或者不选。求不超过容量的前提下能获得的最大总价值
贪心为什么会错? 物品是不可分割的。如果可以分割->贪心
状态设计:dp[ i ][ j ]表示,前 i 件物品中,容量为 j 时的最大价值
转移方程:
如果选第 i 件物品,dp[ i ][ j ] = dp[ i-1 ][ j-w[ i ] ]+v[ i ] (从当前位置的左上角转移)
否则,dp[ i ][ j ] = dp[ i-1 ][ j ]
滚动数组优化:
状态数组的空间开销与物品个数,背包容量有关,很容易空间超限。于是考虑优化空间开销,用一维数组来实现状态数组。
观察转移方程:
发现第 i 行数值只依赖于第 i-1 行。既然前面的都用不上,就把二维压缩成一维,反复覆盖使用
1.采药
for(int i = 1;i<=m;i++){
for(int j = 0;j<=t;j++){
if(j>=w[i]) dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
else dp[i][j] = dp[i-1][j];
}
}
/*
1 2 3 ... 68 69 70
1 0 0 0 ... 0 0 0
2 0 0 0 ... 0 1 1
3 2 2 2 ... 2 2 3
*/
2.Charm Bracelet S
滚动数组
for(int i = 1;i<=n;i++){
for(int j = m;j>=w[i];j--){ // j>=w[i]相当于上题的if
// 从后往前遍历避免上一行的数值已被覆盖
dp[j] = max(dp[j],dp[j-w[i]]+d[i]);
}
}
这里空空如也













有帮助,赞一个