题目链接
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; }
