背包DP(一)——01背包
2026-08-28 16:59:28
发布于：上海
8阅读
0回复
0点赞
01背包：有 n 件物品和一个容量为 V 的背包。第 i 件物品体积为 wi，价值为 vi，每件物品只有一件，只能选或者不选。求不超过容量的前提下能获得的最大总价值。
1.状态设计：dp[i][j] 表示，前 i 件物品中，容量为 j 时的最大价值。
2.转移方程：
· 如果选第 i 件物品，dp[i][j] = dp[i - 1][j - w[i]] + v[i]；
· 如果不选第 i 件物品，dp[i][j] = dp[i - 1][j]；
3.滚动数组优化：状态数组的空间开销，与物品个数、背包容量有关，很容易空间超限。于是考虑优化空间开销，用一维数组来实现状态数组。
观察转移方程：发现第 i 行的数值只依赖于第 i-1行，既然前面的都用不上，就把二维压缩成一维，反复覆盖使用。
方法技巧：通过反向遍历避免重复取值
例题：
A85.采药
错误思路：贪心（性价比）
错误原因：物品不可分割
反例：
假设背包容量为10，
若按贪心思路，应选择①，总价值为7；
而正确答案应选择②③，总价值为10。
| 物品 | 体积w | 价值v | 性价比 |
|---|---|---|---|
| ① | 6 | 7 | 1.17 |
| ② | 5 | 5 | 1.00 |
| ③ | 5 | 5 | 1.00 |
正解：
#include <bits/stdc++.h>
using namespace std;
int t,m;
int dp[110][1010];
int w[110],v[110];
int main(){
cin >> t >> m;
for(int i = 1; i <= m; i++) cin >> w[i] >> v[i];
for(int i = 0; i <= t; i++){
dp[0][i] = 0;
}
for(int i = 0; i <= m; i++){
dp[i][0] = 0;
}
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];
}
}
cout << dp[m][t];
return 0;
}
A573.装箱问题
观察到：数据范围不足以支持二维数组，会MLE，因此采用滚动数组优化
代码：
#include <bits/stdc++.h>
using namespace std;
int v,n;
int w[35];
int dp[20010];
int main(){
cin >> v >> n;
for(int i = 1; i <= n; i++) cin >> w[i];
for(int i = 1; i <= n; i++){
for(int j = v; j >= w[i]; j--){
dp[j] = max(dp[j],dp[j-w[i]]+w[i]);
}
}
cout << v - dp[v];
return 0;
}
这里空空如也
有帮助，赞一个