目录
题目链接：2. 01背包问题 - AcWing题库
问题描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 ii 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数N，V用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
样例
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8题目解析
这是y总的闫氏dp分析法，就是用集合的思想去思考背包问题 ，在状态计算时去划分集合，即可得出状态转移方程。上图中集合里存的是全部的状态，属性的意思是题目中求的是什么，在这道题目中求的是最大值。
遇到dp问题我们首先考虑用几维数组来存储状态，在背包问题中一般是用二维存储，但也有多个条件限制时需要用多维存储。背包问题中建立二维数组f [ i , j ]，i 表示的是拿到了第几个物品，j 表示我们现在可用的体积，所以在这道题目中 i 的范围是1-N，j 的范围是1-V。
我们的思想是用先前更新好的状态去更新没有计算的状态，每个点只更新一遍，不重不漏的更新。并且先拿后者后拿哪个物品是没有区别的，在最优状态下，先拿或后拿都可以，结果不会改变。集合划分就是想怎样用上一个的状态更新现在的状态，在背包问题中，可以以拿不拿第 i 个物品去划分集合，如果不拿第 i 个物品，那么f [ i , j ] 就等于 f [ i -1, j ]，这是因为没拿第i个物品，所以拿的状态就等于拿第i - 1 时的状态；如果拿了第 i 个物品，那么f [ i , j ]就等于f[ i - 1 , j - v [ i ] ] + w[i]，这是因为我们拿了第 i 个，所以回到第 i - 1 状态时体积会减少 v [ i ] ，但是价值会增加 w [ i ] ，所以合并就是状态转移方程，从两个是式子里选一个最大的。
朴素版本
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+10;
int d[N][N],v[N],w[N];
int main()
{
int n,V;
cin>>n>>V; // n 是物品数量 ， V是总可用体积数
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=V;j++){
d[i][j]=d[i-1][j];
// 只有在可用体积大于第i个物品的体积是我们才有机会选他
if(v[i]<=j) d[i][j]=max(d[i][j],d[i-1][j-v[i]]+w[i]);
}
cout<<d[n][V]<<endl; // 在考虑完n种物品和总共的V体积后即可得出最终答案
return 0;
}一维数组版本
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+10;
int d[N],v[N],w[N];
int main()
{
int n,V;
cin>>n>>V;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=V;j>=v[i];j--)
d[j]=max(d[j],d[j-v[i]]+w[i]);
cout<<d[V]<<endl;
return 0;
}在朴素版本中，j 表示可用体积，去掉了表示物品状态的 i ，我们发现我们用第i - 1种物品在不同可用体积下的最优结果去更新第 i 个物品在不同可用体积下的最优结果，当我们到了第 i - 1 个物品的状态时，接下来要去计算第 i 个物品的状态，我们原先是将可用体积从前向后循环，但是我们发现，在计算第 i 个物品时，要用第 i - 1 个物品且可用体积为 j 和 j - v [ i ]的状态，所以我们可以从后向前且只能从后向前更新，因为要是从前向后计算的话，就是用第 i 个物品的状态去更新第 i 个物品的状态，这是不对的，因为一个物品只有一个，选了就不能再选了。
朴素版本与优化版本的区别
1.朴素版本的体积循环既可从前向后循环，又可从后向前循环，因为更新第 i 层不需要改变第 i - 1层；但是优化版本只有一维数组，从前向后的话会丢失第 i - 1 层的数据，导致更新错误，只能从后向前。
2.朴素版本每次体积循环（假设是从小到大循环）都得从1开始循环到 V ，虽然在可用体积大于等于v [ i ] 时才有机会选择第 i 件物品，否则一直都是 f [ i , j ] = f [ i - 1 , j ]，但是必须将第 i - 1 层的信息更新上来，否则第 i + 1 层信息基本上会计算错误。而优化版本中可用体积只用从大到小循环到 v [ i ] 就可以了，这是因为在可用体积小于 v [ i ] 时，根本就不可能选第 i 个物品，所以 f[j]=f[j],不需要去更新，但是循环到1也可以，只需加上判断条件即可，代码如下
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+10;
int d[N],v[N],w[N];
int main()
{
int n,V;
cin>>n>>V;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=V;j>=0;j--)
if(j>=v[i]) d[j]=max(d[j],d[j-v[i]]+w[i]);
cout<<d[V]<<endl;
return 0;
}