背包DP（一）
2026-08-27 11:56:32
发布于：上海
动态规划的经典应用
· 一般来说，就是给定一组由固定价值和固定重量的物品，以及一个承重量固定的背包，求在不超过背包最大承重量的前提下， 能放进背包里面的物品最大总价值。
· 动态规划（DP）类问题主要求解的步骤：
· 1.划分阶段
· 2.确定状态
· 3.确定决策并写出状态转移方程式
· 01背包问题，每个问题只有一件，对每个物体只能选择拿或不拿
贪心为什么错？
根本原因：贪心需要算性价比（单位重量对应的价值），但题中的物品不可分割，所以计算性价比来排序的策略是错的。
所以，也可以考虑01搜索，对每个物品遍历“选or不选”两种情况，但是可能会超时
背包问题的题型分类：01背包，完全背包，多重背包，分组背包......
在CSP-J组时，我们只需要学01背包和完全背包
1.01背包
问题定义：有 n 件物品和一个容量为 V 的背包。第 i 件物品体积 wi ，价值 vi ，每件物品只有一件，只能选或不选，求不超过容量前提下能获得的最大总价值。
状态定义：
dp[i][j] 表示前 i 个物品容量为 j 时的最大价值。
状态转移：
选第 i 个物品 且 容量够，则 dp[i][j] = dp[i - 1][j - w[i]] + v[i]
不选第 i 件物品，则 dp[i][j] = dp[i - 1][j]
dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i-1][j])
答案：一般来说，答案为dp[n][m]
朴素代码的实现：
#include<bits/stdc++.h>
using namespace std;
int t, m;
int dp[105][1005];
int main(){
cin >> t >> m;
for(int i = 1;i<=m;i++){
int w, v;
cin >> w >> v;
for(int j = 0;j<=t;j++){
if(j>=w) dp[i][j] = max(dp[i - 1][j - w] + v, dp[i-1][j]);
else dp[i][j] = dp[i-1][j];
}
}
cout << dp[m][t];
return 0;
}
滚动数组优化：
每次都是覆盖上一行，尝试是否可以使用一维数组进行实现
确定状态：dp[j] 表示背包容量为 j 时的最大价值
#include<bits/stdc++.h>
using namespace std;
int n, m;
int dp[12885];
int w[3500];
int d[3500];
int main(){
cin >> n >> m;
for(int i = 1;i<=n;i++){
cin >> w[i] >> d[i];
}
for(int i = 1;i<=n;i++){
for(int j = m;j>=w[i];j--){
dp[j] = max(dp[j], dp[j-w[i]]+d[i]);
}
}
cout << dp[m];
return 0;
}
有帮助，赞一个