背包DP(一)——01背包
2026-08-28 16:59:28
发布于：上海
14阅读
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;
}
全部评论 1
顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶 顶顶顶顶顶 顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶 顶顶 顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶2026-08-31 来自 上海
1
有帮助，赞一个