01背包问题

闫神视频笔记

视频链接

01背包问题是最基础的背包问题，特点是：每种物品仅有一件，可以选或者不选

题目链接（acwing）

解题思路：

每个物品有选和不选两种选择。我们可以用一个二维数组f[i][j]代表前i个物品，体积为j的最大价值。在体积为j的情况下，如果选择第i个物品，则前i个物品的最大价值为前i-1个物品，在体积为j-第i个物品体积的情况下的最大价值；如果不选择第i个物品，则前i个物品的最大价值为前i-1个物品，在体积为j的情况下的最大价值。而两种选择中的最大值，即为前i个物品在体积为j的情况下的最大价值。最后输出f[n][m]（即前n个物品，体积为m的最大价值）即可。

关于“直接输出f[n][m]的解释：”

f[n][m] 的准确意思是前n个物品中，体积小于等于m的最大价值，f[n][m]为最终答案的前提条件是数组的初始状态都为0。如果只是f[0][0]为0，其他均为-INF，那么在计算过程中，可能会出现错误。比如：在计算f[a][b]时，需要f[a-1][b-v[a]]的数据（其中v[a]代表第a个物品的体积），如果不存在前a-1个物品，体积恰为b-v[a]的情况，那么计算出来的结果就变成-INF+w[a]（其中w[a]代表第a个物品的价值），这样肯定是错误的。以这种方式运算的话，正确的结果就在f[n][j]中，理由就是在最大价值的情况下，体积如果为x，则其最大价值就保存在f[n][x]中，因为我们不知道最大价值的体积是多少，所以我们需要遍历f[n][j]，找出其中的最大值，即是最大价值，而f[n][m]保存的则是前n个物品中，体积恰为m的最大价值（但是题目并不要求体积恰为m）。而为什么将数组的初始状态都设为0，最终结果就是f[n][m]？ 原因就是状态转移的定义从体积恰为m变成了体积小于等于m，这样f[n][m]保存的则是前n个物品中，体积小于等于 m的最大价值，故其一定正确。

代码：

#include<iostream> #include<cstring> #include<string> #include<algorithm> #include<vector> #include<map> #include<queue> #include<cstdio> #include<cmath> using namespace std; const int N = 1010; int f[N][N];//前i个物品，总体积为j的最大价值 int v[N],w[N];//保存物品的体积与价值 int main(){ // freopen("1.txt","r",stdin); int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>v[i]>>w[i]; for(int j=1;j<=m;j++){ if(v[i]<=j){ f[i][j]=max(f[i-1][j-v[i]]+w[i],f[i-1][j]); }else{ f[i][j]=f[i-1][j]; } } } cout<<f[n][m]<<endl; return 0; }

优化空间复杂度:O(N*V)->O(V)

原理：

通过观察其运算过程可以发现，计算前i个物品的最大价值的过程中，只有第i-1行的数据是需要被用到的。而当计算体积为j的情况时，第i-1行的数据中只有体积小于等于j的数据可能会被用到。因此我们可以按体积递减的顺序进行，计算前i个物体，体积为j的最大价值时，将结果保存在下标为j的位置中（原本保存的是前i-1个物体，体积为j的最大价值，本次运算结束后，该数据就不会再被用到，所以可以用来保存新得出的数据）

改进之后的代码：

#include<iostream> #include<cstring> #include<string> #include<algorithm> #include<vector> #include<map> #include<queue> #include<cstdio> #include<cmath> using namespace std; const int N = 1010; int f[N];//体积为i的最大价值 int v[N],w[N];//保存物品的体积与价值 int main(){ // freopen("1.txt","r",stdin); int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>v[i]>>w[i]; for(int j=m;j>=v[i];j--){ f[j]=max(f[j],f[j-v[i]]+w[i]); } } cout<<f[m]<<endl; return 0; }