动态规划之背包问题
作为算法界的经典，背包问题一直是动态规划的一个代表，也是给了无数算法新人一记迎头痛击啊，我也是被其困扰了好长一段时间，连最基础的模板都很难理解，更别说无尽的变体了，今天我就来带大家回顾一下基础模板的思路。
01背包
题面：
N件物品和一个容量是V的背包。每件物品只能使用一次。第
i件物品的体积是v[i]，价值是w[i]。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
代码：
int main()
{
int n, m, v[1010] = { 0 }, w[1010] = { 0 }, dp[1010]= { 0 };
scanf("%d %d", &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--)
dp[j] = max (dp[j], dp[j - v[i]] + w[i]);
printf("%d", dp[m]);
return 0;
}
题解：
状态转移方程：dp[j] = max (dp[j], dp[j - v[i]] + w[i]);
考虑前i个物品在空间为j的情况下的最优解，要加入当前物品需要预留空间，则将当前与腾出空间后加上当前物品价值对比得出当前最优解。
值得注意的是第二层j循环从大到小遍历直到不可能装下当前物品，若从小到大则可能会发生前面的情况影响后面的情况，导致一件物品被装入多次，而从大到小则不会。
二维01背包
题面：
航天飞机的体积有限，当然如果载过重的物品，燃料会浪费很多钱，每件食品都有各自的体积、质量以及所含卡路里。在体积和质量的最大值的情况下，请输出能达到的食品方案所含卡路里的最大值，当然每个食品只能使用一次。
代码：
int main()
{
int H, T, n;
scanf("%d %d", &H, &T);
scanf("%d", &n);
int h[60], t[60], k[60], dp[500][500] = { 0 };
for (int i = 1; i <= n; i++)
{
scanf("%d %d %d", &h[i], &t[i], &k[i]);
for (int j = H; j >= h[i]; j--)
for (int m = T; m >= t[i]; m--)
dp[j][m] = max(dp[j][m], dp[j - h[i]][m - t[i]] + k[i]);
}
printf("%d", dp[H][T]);
return 0;
}
题解：
状态转移方程：dp[j][m] = max(dp[j][m], dp[j - h[i]][m - t[i]] + k[i]);
在01背包的基础上，dp数组多开一维度，多进行一层循环，在这题中，dp[j][m]中j表示体积，m表示质量。
同样是从大到小遍历防止同一个食物放入两次。
完全背包
题面
N件物品和一个容量是V的背包。每件物品可无限使用。第
i件物品的体积是v[i]，价值是w[i]。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
代码：
int main()
{
int n, m, v[1010] = { 0 }, w[1010] = { 0 }, dp[1010]= { 0 };
scanf("%d %d", &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 printf("%d", dp[m]);
return 0;
}
题解：
状态转移方程：dp[j] = max (dp[j], dp[j - v[i]] + w[i]);
和01背包不同，第二层j循环从小到大，用多装的情况覆盖少的情况，正好可以考虑无限次数的使用。
多重背包
题面
有
N种物品和一个容量是V的背包。第i种物品最多有
s[i]件，每件体积是v[i]，价值是w[i]。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
代码：
int main()
{
int n, m, dp[1010] = { 0 }, s[1010] = { 0 }, w[1010] = { 0 }, v[1010] = { 0 };
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d %d %d", &v[i], &w[i], &s[i]);
for (int i = 1; i <= n; i++)
for (int j = m; j >= 1; j--)
for (int k = 0; k * v[i] <= j && k <= s[i]; k++)
dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
printf("%d", dp[m]);
return 0;
}
题解：
状态转移方程：dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
多重背包类似01背包，将多个相同的物体拆开来考虑，我们只需要在01背包的基础上，加入第三层循环，来考虑每个物体放入的个数，即可完成此题，但当数据量过大时，O（n³）的复杂度显然是难以接受的，所以在多重背包我们往往会用到二进制优化。
多重背包——二进制优化
题面
有
N种物品和一个容量是V的背包。第i种物品最多有
s[i]件，每件体积是v[i]，价值是w[i]。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
代码：
int main()
{
int n, m, dp[2010] = { 0 }, w[2010] = { 0 }, v[2010] = { 0 };
int a, b, c, count = 1;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d %d %d", &a, &b, &c);
for (int j = 1; c > j; j *= 2)
{
v[count] = j * a;
w[count] = j * b;
count++;
c -= j;
}
v[count] = c * a;
w[count] = c * b;
count++;
}
count--;
for (int i = 1; i <= count; i++)
for (int j = m; j >= v[i]; j--)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
printf("%d", dp[m]);
return 0;
}
题解：
状态转移方程：dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
根据二进制的性质，我们完全可以用二进制的形式来表达一个数，或者更简单，我们只需要用二进制表达其中的一部分，使得比这个数小的任何数都能被这几个部分组成即可，这样，我们就通过数个组分的组合，完成了所有可能的数量。
如上，我们用若干偶数和一个余数，将所有的物体给拆分为若干组分，每个组分的体积和质量的都是单个物体的若干份，这样，我们就将多重背包转换为了01背包。
分组背包
题面
有
N种物品和一个容量是V的背包。每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是
v [i][j]，价值是w[i][j]，其中i是组号j是组内编号。。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
代码：
int main()
{
int n, m,s, v[1010] = { 0 }, w[1010] = { 0 }, dp[1010] = { 0 };
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &s);
for (int j = 1; j <= s; j++) scanf("%d %d", &v[j], &w[j]);
for (int j = m; j > 0; j--)
for (int k = 1; k <= s; k++)
if (j >= v[k])
dp[j] = max(dp[j], dp[j - v[k]] + w[k]);
}
printf("%d", dp[m]);
return 0;
}
题解：
状态转移方程：dp[j] = max(dp[j], dp[j - v[k]] + w[k]);
分组背包与01背包类似，我们分组考虑，在某一组考虑完之后我们再进入下一组，第二层循环从大到小遍历直到不可能装下当前组物品，因为从小到大装会导致同一组装入多个物品，已经装入的东西会影响后面的情况。
总结
以上便是背包问题模板的总结，本文由凉茶coltea撰写，转载请注明出处。请注明出处。