动态规划之背包问题
01背包
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
枚举：我们可以用0和1来表示当前物品是不是取了，0表示没有取，1表示取了，比如说有三个物品，001，那么001表示第一个物品取了，第二个和第三个物品都没有取
当我们考虑了前i个物品取还是不取的情况，如果有两组方案的体积是一样的，保留最大收益的即可。
考虑了前i个物品，总体积为j的情况分为两种：
1.第i个物品没有取，就是考虑前i-1体积为j的情况
2.第i个物品取了，就是考虑前i-1体积为j-v[i]的情况
最有子结构：为了计算前i个物品且体积为j的情况下收益的最大值，我们可以先考虑上一个状态i-1的最大值，前i-1个物品的状态也分为两个状态体积为j和j-v[i]的最大收益。
无后效性：之考虑最值，不考虑是拿了哪些物品而得到的最大值
状态：f[i][j]表示考虑拿前i个物品，总体积为j的最大收益
转移：f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])
AC代码：
#include<iostream>
using namespace std;
const int N = 1010;
int v[N],w[N], f[N][N],n,m;
int main(void)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &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 - 1][j], f[i - 1][j - v[i]] + w[i]);
}
}
}
cout << f[n][m] << endl;
return 0;
} 思考：
真的需要开这么大的数组吗？有没有可以优化的地方
考虑前i个物品时的状态之和考虑了前i-1个物品的状态有关，前面的i-2是不需要被记录的。
数据跟踪代码：
#include<iostream>
using namespace std;
const int N = 1010;
int v[N],w[N], f[N][N],n,m;
int main(void)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &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 - 1][j], f[i - 1][j - v[i]] + w[i]);
printf("f[%d][%d]= %d f[%d][%d]= %d f[%d][%d]+w[%d]= %d\n", i, j, f[i][j], i - 1, j, f[i - 1][j], i - 1, j - v[i], i, f[i - 1][j - v[i]] + w[i]);
}
}
}
cout << f[n][m] << endl;
return 0;
}
优化后的代码：
#include<iostream>
using namespace std;
const int N = 1010;
int v[N],w[N], f[N],n,m;
int main(void)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &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]);
}
puts("");
}
cout << f[m] << endl;
return 0;
}我们来看一下二维的转移方程
f[i][j]=f[i-1][j];//没有取第i个物品
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);//取了第i个物品f[i][j]=f[i-1][j]可以等效于f[j]=f[j]，这个式子是恒成立的，所以可以直接不写
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]);但如何去得到i-1和i轮的数据呢？
我们可以把枚举体积的状态逆向更新，原本是从小到大更新，现在从大到小更新，因为j-v[i]一定是比j要小的，所以当我们更新j的时候用到的j-v[i]是更小的数，也就是还没有在当前这一轮被更新掉，就是上一轮的值，所以可以进行压缩。我们来跟踪一下代码：
跟踪代码：
#include<iostream>
using namespace std;
const int N = 1010;
int v[N],w[N], f[N],n,m;
int main(void)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &v[i], &w[i]);
}
for (int i = 1; i <= n; i++)
{
for (int j = m; j>=v[i]; j--)
{
printf("更新前的 f[%d]= %d ", j, f[j]);
f[j] = max(f[j], f[j - v[i]] + w[i]);
printf("更新之后的 f[%d]= %d f[%d]+w[%d]= %d 加入的物品体积为：%d\n",j,f[j], j-v[i],i,w[i],v[i]);
}
puts("");
}
cout << f[m] << endl;
return 0;
}
完全背包
完全背包和01背包的不同之处在于完全背包的每一件物品可以使用无限次。
我们依旧把考虑了前i件物品之后，总体积为j的所有情况的最大收益记录下来
在考虑前i种物品，总体积为j的时候分为两种情况：
1.第i种物品没取，也就是考虑前i-1种物品总体积为j的情况。
2.第i种物品取了，也就是考虑前i种物品总体积为j-v[i]的情况。
状态：f[i][j]表示考虑了前i件物品体积为j的时候的最大收益
转移：f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i])。
我们来对比一下01背包和完全背包的状态转移方程的区别：
01背包：
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
完全背包:
f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
//区别就在于01背包是[i-1]完全背包是[i]，完全背包考虑第i个物品可以取多次
AC代码：
#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N], f[N][N], n, m;
int main(void)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &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 - 1][j], f[i][j - v[i]] + w[i]);
}
}
}
cout << f[n][m] << endl;
return 0;
}接下来我们对代码进行数据追踪： 
可以看到，第i个物品可以被选择多次，然后通过对比体积相同的时候出现的两种情况取一个最大值即可。
跟踪代码：
#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N], f[N][N], n, m;
int main(void)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &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 - 1][j], f[i][j - v[i]] + w[i]);
}
}
for (int j = 0; j <= m; j++)
{
//if (j - 1 < 0 || j - v[i] < 0) continue;
printf("f[%d][%d]=%d f[%d][%d]=%d f[%d][%d]= %d f[%d][%d]+w[%d]= %d \n",i,j,f[i][j],i-1,j,f[i-1][j], i - 1, j, f[i - 1][j], i, j - v[i], i, f[i][j - v[i]] + w[i]);
}
puts("");
}
cout << f[n][m] << endl;
return 0;
}那么完全背包是否也可以像01背包那样把数组压缩一下呢？
优化后的代码
#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N], f[N], n, m;
int main(void)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &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] << endl;
return 0;
}为什么完全背包的j可以正序遍历，而01背包却要逆序遍历呢?
我们来看一下01背包和完全背包的二维状态转移方程：
01背包：
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
完全背包：
f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
01背包要的全都是上一层i-1的数据，而完全背包一个需要第i层的数据，一个需要第i-1层的数据。
但完全背包当中需要第i-1层数据的背包容量为j，而需要第i层数据的背包容量为j-v[i]，显然j>j-v[i]，所以需要第i层数据的在后面，需要第i层数据的在前面。我们对数据进行跟踪：
我们可以看到，红色框框中的f[4]，更新f[4]所用到的f[4]是上一轮的f[4]，更新所用到的f[2]是当前这一轮的f[2]，从图中也可以看出来，f[2]已经比f[4]先被更新掉了。
跟踪代码：
#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N], f[N], n, m;
int main(void)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &v[i], &w[i]);
}
for (int i = 1; i <= n; i++)
{
for (int j = v[i]; j <= m; j++)
{
printf("更新前：f[%d]=%d f[%d]+w[%d]=%d \n", j, f[j], j - v[i], i, f[j - v[i]] + w[i]);
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
for (int j = 0; j <= m; j++)
{
printf("更新后：f[%d]=%d f[%d]+w[%d]=%d \n", j, f[j], j - v[i], i, f[j - v[i]] + w[i]);
}
puts("");
}
cout << f[m] << endl;
return 0;
}
多重背包I
因为每个物品可以拿l[i]次，那么我们可以把这个物品拆分成l[i]个物品，这样就将多重背包转换为01背包了
思路和01背包一样，只是多了一层循环来将可以拿l[i]次的物品变成l[i]个物品。
AC代码：
#include<iostream>
using namespace std;
const int N = 1010;
int f[N], v[N], w[N], l[N], n, m;
int main(void)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> v[i] >> w[i] >> l[i];
}
for (int i = 1; i <= n; i++)
{
for (int k = 1; k <= l[i]; k++)
{
for (int j = m; j >= v[i]; j--)
{
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
}
cout << f[m];
return 0;
}虽然问题解决了，但这for循环确实多的吓人啊，三层for循环，时间复杂度直接
$$
O(N^3)
$$
如果这道题目数据量小还是可以解决的，如果数据量大于1000了，1000*1000*1000=1000000000十亿的循环次数是绝对会超时的。
多重背包II
如果数据量很大的时候，就需要对其进行优化，能够进行优化的点就是在将一个能取l[i]次物品分成l[i]个物品，然后取x个这个物品的时候，不一定需要一个一个地去遍历，我们可以像计算机存储数字的二进制一样，通过一些数字来组合成你想要的数字。
假设有50个苹果，现在要拿n个苹果出来(n<=50)，如何取？
最朴素的做法就是将苹果一个一个地拿出来，直接取了n个苹果。
再假设我们有50个苹果和6个箱子，箱子中可以装1、2、4、8、16、19(19就是剩余的数)，当我们取任意n个苹果的时候只需要推出来几个箱子就行了。
二进制拆分思想：
将第i个物品拆分成若干件物品，每件物品的体积和价值乘以一个拆分系数：
$$
2^0、2^1、2^2、2^3、2^4、2^5……2^n
$$就可以转换成01背包的物品求解。例如Si=12，拆分系数就是1，2，4，5，转换成了4件01背包的物品：
(v[i]，w[i])，(2v[i]，2w[i]，,(3v[i]，3w[i])，(4v[i]，4w[i])
例如输入数据:
3 7
2 3 12
3 5 15
1 2 3
列出二进制表格：
2 3 12的情况
3 5 15的情况
1 2 3的情况
AC代码：
#include<iostream>
using namespace std;
const int N = 100010;
int f[N], v, w, l, n, m, vv[N], ww[N];//vv[]存体积，ww[]存价值
int main(void)
{
scanf("%d %d", &n, &m);
int num = 1;//统计拆分次数
for (int i = 1; i <= n; i++)
{
cin >> v >> w >> l;
//二进制拆分
for (int j = 1; j <= l; j *= 2)//j就是系数
{
vv[num] = j * v;//存体积
ww[num++] = j * w;//存价值
l -= j;
}
if (l)//如果还有剩余的
{
//l就是剩下的数
vv[num] = l * v;
ww[num++] = l * w;
}
}
for (int i = 1; i < num; i++)
{
for (int j = m; j >= vv[i]; j--)
{
f[j] = max(f[j], f[j - vv[i]] + ww[i]);
}
puts("");
}
cout << f[m];
return 0;
}二进制优化时间复杂度：
$$
m\sum logli\\
$$
多重背包III
我们对朴素算法进行逆序追踪可以看到f[x]都是由f[x-k*v]更新而来的，所以我们可以将f数组按类更新，可以把f[0……m]按照体积v的余数拆分成v个类。
f[0],f[v],f[2v]......f[kv];
f[1],f[v+1],f[2v+1]......f[kv+1];
f[2],f[v+2],f[2v+2]......f[kv+2];
f[j],f[v+j],f[2v+j]......f[kv+j];
加入v=2，
f[0],f[2],f[4],f[6]...为一类
f[1],f[3],f[5],f[7]...为一类
f[j]是由前面不超过数量s的同类值递推得到的这就相当于在一个长度为l的滑动窗口当中去挑选最大值来更新当前值。所以，我们可以用一个单调队列来维护这个窗口最大值，从而减少f[j]的更新次数（减少到1次）。
单调队列是从小到大进行滑动，那么窗口也要从小到大进行更新，也就是只能顺序遍历背包容量j。而顺序更新f值就会导致数据被污染，所以我们需要多开一个备份数组g。
AC代码：
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int v, w, s, q[N], f[N], g[N], n, m;
int main(void)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
memcpy(g, f, sizeof f);
cin >> v >> w >> s;
for (int j = 0; j < v; j++)//拆分成v类
{
int h = 0, t = -1;//h是对头，t是队尾
for (int k = j; k <= m; k += v)//k是下标编号
{
//窗口的大小为[k-s*v,k-v]
if (h <= t && q[h] < k - s * v) h++;
//(k-q[h])是编号之间的差值，用差值/V就是能够放入背包的数量，数量乘以单价就是总价值
if (h <= t) f[k] = max(g[k], g[q[h]] + (k - q[h]) / v * w);
//如果用g[k]比用g[q[t]]更新f[x]的收益更大，那么队尾元素pop掉
while (h <= t && g[k] >= g[q[t]] + (k - q[t]) / v * w) t--;
//入队
q[++t] = k;
}
}
}
cout << f[m];
return 0;
}
分组背包
考虑前i组物品之后，总体积为0，1，2，3，4，5，......，m时的最大收益都记下来
考虑前i组物品，总体积为j的时候分为两种情况:
1.第i组中一个物品都没有取，考虑前i-1组物品，总体积为j时的情况
2.第i组中取了一个物品，枚举其中的k件物品，问题变成了考虑前i-1组物品，总体积为j-v[k]时的情况
状态：用f[i][j]表示考虑前i组物品，总体积为j时的最大收益。
转移：f[i][j]=max(f[i-1][j],f[i-1][j-v[k]]+w[k])
AC代码：
#include<iostream>
using namespace std;
const int N = 110;
int f[N][N]; //只从前i组物品中选，当前体积小于等于j的最大值
int v[N][N], w[N][N], s[N]; //v为体积，w为价值，s代表第i组物品的个数
int n, m, k;
int main(void)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> s[i];//当前组有多少个元素
for (int j = 0; j < s[i]; j++)
{
cin >> v[i][j] >> w[i][j];
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
f[i][j] = f[i - 1][j];
for (int k = 0; k <s[i]; k++)
{
if (j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
}
}
}
cout << f[n][m];
return 0;
}