什么是背包问题？
- 背包问题简单讲就是我们有一个确定容量的背包，有n件物品，每件物品的有确定的价值和体积，问我们在不超出背包容量的前提下，可以带走物品的最大价值是多少。虽然问题很简单，但是根据物品的选择要求不同，可以细分为：01背包问题、完全背包问题、多重背包问题、分组背包问题和混合背包问题。我们一个一个来看。
01背包问题
什么是完全背包？
- 01背包是背包问题中最基础的问题。名字前有个
01，顾名思义就是每个物品要么选0次（不选），要么选1次。
一个陷阱！
- 有同学可能已经想到了贪心，求出所有物品的性价比，然后从高到低排序，依次取性价比最高的物品放入背包直到不能再放入物品。看样子没有任何问题，但是这位同学已经陷入了误区，让我们看这个例子：背包容量80，有3种物品，价值和体积分别是：
30 50、50 90、60 120，如果贪心来做显然只能取体积为60的物品，价值为120，而实际上我们可以取体积为30和50的物品，价值有140！问题出在哪里？贪心不能保证将背包填满，导致背包中的空闲部分拉低了整个背包中物品的平均价值。
如何求解？
- 我们用
f[i][j]表示前i个物品在不超过体积j的前提下的所有方案的集合，然后取集合的最大值。 - 因为每个物品要么不选，要么只能选1次，所以我们可以根据是否选第
i件物品来将整个集合分为两个子集，不选第i件物品的最大价值：f[i-1][j]，选第i件物品的最大价值：f[i-1][j-vi]+wi。v[i]和w[i]分别是第i件物品的价值和体积。 - 那么就得到状态转移方程：
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
如何优化？
- 考虑进行优化，我们可以发现状态转移方程中只用到了上一层的计算结果，那么我们开二维数组其实是浪费了很多空间的。如何优化？考虑用滚动数组，既然只用到了上一层的结果，那么我们直接将所有的数据都存在一个一维数组中。
- 注意方程的左值是
f[j]，右值中含有f[j-vi]如果我们将仍旧将容量从小到大更新f[j]，那么将会有在某次更新f[j]用到的f[j-vi]是之前被更新过的f[j]，那么我们就无法保证数据的正确性。如何解决？我们的目的是保证每次用到的f[j-vi]都是上一层的，那么每次更新数据时我们可以从后向前更新，因为f[j-vi]是一定不大于f[j]的，那么就能保证状态转移方程中的f[j-vi]的正确性。
未优化代码
状态转移方程：f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int m,n;
int w[N],v[N];
int f[N][N];
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=1;j<=m;++j)
{
f[i][j]=f[i-1][j];//继承上一次循环的结果
if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
cout<<f[n][m];
return 0;
}状态压缩优化代码
状态转移方程：f[j]=max(f[j],f[j-v[i]]+w[i]);
为了保证状态转移方程用到的 f[j-v[i]] 是上一次的结果，j（容量）要从大到小循环
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int m,n;
int w[N],v[N];
int f[N];
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=m;j>=v[i];--j)
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
cout<<f[m];
return 0;
}完全背包问题
有趣的小技巧 ：将优化后01背包代码中的 for(int j=m;j>=v[i];--j) 改成 for(int j=v[i];j<=m;++j) 可以直接拿来当完全背包用。也许有同学觉得，诶这怎么啦，不都是背包问题嘛，可以求解很正常吧。但是看完什么是完全背包问题也许就会觉得，哇这好离谱啊。而看完为什么后也许又会觉得，确实是这么回事，就该这样。
什么是完全背包？
- 完全背包问题就是所有物品不再有数量限制，每种物品均可以在容量范围内无限取。
如何求解？
-
我们可以发现完全背包实际上就是01背包的基础上取消了物品的数量限制，那么我们就可以用01背包的思路来求解完全背包问题。
-
仍然用
f[i][j]表示前i个物品在不超过j容量的前提下，所有取法的集合。 -
完全背包问题同样根据第i件物品划分子集。但由于每件物品可以取无限件，那么在划分子集时就不能像01背包那样简单分为两个子集，完全背包问题根据第i件物品取的件数不同，划分为k个集合，k∈[0, V/v[i]]，也即第i件物品可以不取（
f[i-1][j]），也可以一直取到仅用第i件物品填满背包（f[i-1][j-v[i]*k]+w[i]*k; k=V/v[i]）。 -
那么我们就可以得到状态转移方程：
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-v[i]*2]+w[i]*2,...,f[i-1][j-v[i]*k]+w[i]*k); -
看上去似乎有些长？别急，我们根据上式继续写出
f[i][j-v[i]]的状态转移方程：f[i][j-v[i]]=max( f[i-1][j-v[i]],f[i-1][j-v[i]*2]+w[i],...,f[i-1][j-v[i]*(k-1)]+w[i]*(k-1)); -
对比两式是否发现了什么端倪？是的，下式与上式除去第一项外的部分几乎相同，那么我们就可以将
f[i][j]的状态转移方程简化为f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
如何优化？
- 因为完全背包同样只用到两层，所以可以用滚动数组优化。
- 直接去掉前i个物品这一维，原式变为：
f[j]=max(f[j],f[j-v[i]]+w[i]);似乎和01背包相同，但是但是要明确两者是由谁转移过来的，01背包是由上一层的结果转移过来，而完全背包是由当前这一层转移过来的（注意观察初始状态转移方程中前i个物品这一维），所以在循环空间时，01要由大到小保证当前层没有被计算过，而完全背包要由小到大保证当前层已经计算过。
未优化代码
未优化版本仅用来助于理解思路，因为涉及三种循环一般必超时，01背包优化属于为了美观而优化，而完全背包不得不优化。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
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)
for(int k=0;k*v[i]<=j;++k)
f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
}
cout<<f[n][m];
return 0;
}状态压缩优化代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int m,n;
int w[N],v[N];
int f[N];
int main()
{
int n,m;
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=v[i];j<=m;++j)
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
cout<<f[m];
return 0;
}总结
- 01背包问题：
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]); - 优化版本：
f[j]=max(f[j],f[j-v[i]]+w[i]); - 完全背包问题：
f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]); - 优化版本：
f[j]=max(f[j],f[j-v[i]]+w[i]);
多重背包问题
二进制优化多重背包：梧桐苑|多重背包 II
