题目链接
2. 01背包问题 - AcWing题库
一些话
切入点
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
0<N,V≤1000
0<vi,wi≤1000
1.求解某种符合题意的方案,而且是要最优方案,符合dp特征
2.数据范围在1e3内,属于dp的范畴
流程
闫氏dp分析法
分析问题分为状态表示和状态计算两部分
1.状态表示,思考用1维还是2维来储存数据,此题有物品,空间和价值三种数据要储存,所以宜选用2维
状态表示后又分为集合和属性两部分
1.1集合:二维数组f[i][j]表示一个怎样的集合? 01背包中表示物品的选法
考虑前i个物品的情况下,背包容积还剩j时的最优解
1.2属性:二维数组f[i][j]储存的数据是什么属性 maxn?minn?数目?此题储存的是maxn
(状态表示部分往往是靠经验来写而不是自己想出来的)
2.状态计算:
将集合划分成子集合,来一层一层获取
划分的依据是:最后一个不同的节点,如此题是f[i][j]选不选i,选和不选是两种结果
每层的选与不选可以将集合划分为两个子集,没有遗漏。(求数量时还有遵循不重复的原则)
选i,[i-1][j-v[i]] + w[i];
不选[i-1][j];
最后按照分析的结果枚举每一层,输出f[n][m];
套路
ac代码
// 11:01~11:08 #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; // f[i][j],考虑前i件物品,背包容量j时的价值 const int N = 1e3 + 10; int f[N][N]; int v[N],w[N]; int n,m; int main(){ cin >> n >> m; for(int i = 1;i <= n;i++){ cin >> v[i] >> w[i]; } for(int i = 1;i <= n;i++){ for(int j = 0;j <= m;j++){ f[i][j] = f[i-1][j]; if(v[i] <= j){ f[i][j] = max(f[i][j],f[i-1][j-v[i]] + w[i]); //在纠结这里为什么是f[i-1][j-v[i]] + w[i], // 会纠结的根本原因是没明白f[i][j]的含义,考虑前i件物品,背包还剩下j空间时的最优解 // 因为能选的物品都考虑过后才可能得到一个最优解,所以只有上一层i的数值是正确的,所以只能用f[i-1]的值,不能用f[i]的值 } } } cout << f[n][m] << endl; return 0; }