0-1背包 最多用一次
完全背包 每件物品有无限个
多重背包 每个物品个数不一样 优化
分组背包问题
0-1背包
题目：
0-1背包一维优化
因为，状态转移中只使用了f[i-1]和f[i] ，其他的没用，所以说我们可以使用滚动数组来优化，把f[i][j]改成f[j]，不考虑其他的i的存储。
原代码
for(int i = 1;i <= n; i++)
for(int j = 0; j <= m;j++)
{
f[i][j] = f[i-1][j];//保持与上一层i相同，所以直接删掉
if(j >= v[i]) f[i][j] = max(f[i-1][j], f[i-1][j-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]);
}
由于状态改变需要j >= v[i]，所以直接令j从v[i]开始循环。但是由于j是递增循环，j-v[i]肯定小于j，所以f[j-v[i]]指的是第i层的值。而原式是f[i-1]，所以将第二层循环改成递减。
完全背包问题
完全背包 每件物品有无限个
朴素版
k为第i个物品的个数，状态转移方程为$f[i,j] = f[i - 1], j - v[i] * k] + w[i] * k$
for(int i = 1;i <= n; i++)
for(int j = 0; j <= m;j++)
for(int k = 0;v[i] * k <= j;k++)
f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);//当k = 0时即i物品不放入的情况
运行时间过长，时间复杂度较大
二维优化
由图所得，优化后状态转移方程为$f[i, j] = Max(f[i - 1, j], f[i, j - 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(j >= v[i]) f[i, j] = Max(f[i, j],f[i, j - v[i]] + w[i]);
}
一维优化
类似0-1背包问题，将数组变为一维，但完全背包问题不同于0-1背包，状态转移方程中为f[i, j - 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]);
完整推导过程如上
综上，0-1背包问题与完全背包问题的区别，仅仅只在第二层循环，0-1背包中j为从大到小递减循环，完全背包中j为从小到大递增循环。
为什么二者只有这个不同点？我不到啊
多重背包
二进制优化
思路：
将每种物品的s个分割成2的指数相互组合
$1,2,4,8,16……,2^{k} ,c，且2^{k} <s,2^{k+1} >s$，
$1-2^{k}$ 可组合覆盖到$2^{k+1} -1$，有$c<2^{k+1}$ 使得$2^{k+1} -1+c = s$ 实现s的拆分
n种物品，每个s[i]个，全部组合成个数为$\log{s}$的小组合体（新的物品，拥有新的价值和体积），将这些小组合体进行0-1背包求解。
int cnt = 0;
//拆分
for(int i = 1;i <= n;i ++ )
{
int a, b, s; //a是物品体积 b是物品价值 s是物品个数
cin >> a >> b >> s;
int k = 1;
while(k <= s)
{
cnt ++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if(s > 0)
{
cnt ++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt;
//0-1背包
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]<<endl;