[动态规划] 背包问题归纳

一、01背包问题

1. 定义

有n件物品和一个容量为V的背包。第i件物品的体积（volumn）是v[i]，价值（worth）是w[i]，问如何选择物品装入背包可使价值总和最大。

2. 解析

• 每种物品只有选和不选两种。我们可以使用多阶段动态规划的思想来解决。
  用dp[i][j]表示前i个物品（或用“从第i个物品开始的后面所有物品”的反向定义也行）装入容量为j的背包中的最大价值量。
  则转移方程为：
  
  其中每多考虑一个物品i，代表一个“阶段”。括号第一项表示选，第二项表示不选。

• （优化）由于每一项都是依赖于i-1，因此可以使用滚动数组来优化空间复杂度：
  
  其中注意使用滚动数组时，j的遍历必须逆序，来保证等号右边使用的dp值是上一阶段的结果值.

• 如果需要打印路径，则必须使用第一种写法，否则可以使用优化写法来节省空间。

3. 模板

• 普通写法

int V, n, v[maxn], w[maxn], dp[maxn][maxv];

for(int j = 0; j <= V; j ++) dp[0][j] = 0;
for (int i = 1; i <= n; i ++) {
    for (int j = v[i]; j <= V; j ++) {
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
    }
}

• 优化写法

int V, n, v[maxn], w[maxn], dp[maxv];

for (int i = 1; i <= n; i ++) {
    for (int j = V; j >= w[i]; j --) {  // 逆序遍历
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
}

4. 例题

Uva 624： https://blog.nowcoder.net/n/a80587c9c2204f40bc802e4403db9587
Luogu 2925 干草出售
Luogu 1616 疯狂的采药
Hdu 3466 Proud Merchants

二、完全背包问题

1. 定义

有n种物品和一个容量为V的背包，每种物品都有无限个。第i种物品的体积为v[i]，价值是w[i]。问如何选择物品装入背包可使价值总和最大。

2. 解析

• 由于有无限个，所以每种物品的选择就有无限种了，因此我们不能用01背包的套路了，需要换一种思路。我们先回顾一下01背包中的优化写法，之所以j要逆序遍历是为了使得等号右边的dp值对应的是上一物品计算完后的dp值。而回到完全背包问题，由于物品有无限个，因此对于已经选择了当前物品的dp值，我们依然可以继续添加当前物品，直到达到背包上限为止。这样一想，完全背包问题的递推式就大概是：
  
  其中第1、2项和01背包一样，第3项表示继续添加当前物品。

• 然而上述递推式实在是比较混乱，因此实际上大多数情况下使用的是滚动数组的版本：
  
  可以看到这里和01背包的转移方程是一样的，但是实际用的时候这里j的遍历顺序必须为正序。

• 在笔者看来，完全背包问题的写法其实还可以通过刷表法来理解。就是对于每一种新的物品i，用它来不断刷新所有体积的背包的状态（最大价值量）。j的顺序遍历使得刷新的效果可以“叠加”，从而实现放入多个物品的效果。

• 实际上紫薯还提供里完全背包的另一种思路，即看成是带权的DAG的最长路问题，不过其代码量相比于递推式要稍微大一些，因此这里略。感兴趣的可以看一下下面的例题，有使用了这种方法的题解。

3. 模板

int V, n, v[maxn], w[maxn], dp[maxv];

fill(dp, dp + V + 1, 0);
for(int i = 1; i <= n; i ++) {
    for(int j = v[i]; j <= V; j ++) {  // 顺序遍历
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
}

4. 例题

Hdu 4508：https://blog.nowcoder.net/n/f52f039856de40f798b881ac15e0a346
Hdu 1114 Piggy-Bank
Luogu 1853 投资的最大效益

三、多重背包问题

1. 定义

有n种物品和一个容量为V的背包。第i种物品最多有p[i]件可用，每件体积是v[i]，价值是w[i]。问如何选择物品装入背包可使价值总和最大。

2. 解析

• 多重背包问题限制了物品的数目，这里有一种显然的思路就是，把每一“个”物品看作一个不同的“种”物品，然后用01背包去做，但是这样大概率为超时（笑），时间复杂度为O(V*∑p[i])

• 顺着上述思路，有一种二进制法可以将时间复杂度降到O(V*∑lgp[i])，并且一般够用了😀。
  它的原理就是将一个数量为p[i]，价值为v[i]的物体拆分成 1、2、4、8...这若干份（每一份右2的幂次份原物体构成，构成的新物体价值为kw[i]，体积为kv[i]），然后 注意最后不足2的幂次的数量也单独做成1份，这样物体的总数量就降为了 O(∑lgn)。然后就可以按照01背包问题的套路来处理这∑lgn个新物体了。
  正确性是由二进制原理保证的：因为原来可能选择的1~p[i]个原物体一定可以被替换为新物体的组合。

• 实际上还有一种使用单调队列的优化方式，但由于技巧性比较高，一般用不到

3. 模板

int V, n, v[n], w[n], p[n], dp[maxv];  // p[i]表示原物体i的数量限制

fill(dp, dp + V + 1, 0);
for(int i = 0; i < n; i ++) {
    for(int k = 1, num = min(p[i], V / v[i]); num > 0; k <<= 1) {  // 每一个新物体由k个原物体组成
        if(k > num) k = num;  // 最后不足2的幂次的单独一份
        num -= k;
        for(int j = V; j >= k * v[i]; j --) {  // 对新物体使用01背包问题处理，这里使用的是01背包问题的滚动数组模板，当然也可以不用
            dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
        }
    }
}

其实还有另一种写法是将原物体分为新物体后用一个新数组装起来，然后再进行01背包操作，区别其实不大。这里直接写在外层嵌套了，因为代码量少一些所以我喜欢😀。

4. 例题

Hdu1059：https://blog.nowcoder.net/n/435420c882a44e2881fa142ebf83ba94
Luogu P1776 宝物筛选

四、混合背包问题

1. 定义

如果将前面三种背包问题混合起来，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的有限次（多重背包），问如何选择物品装入背包可使价值总和最大。

2. 解析

• 首先01背包和多重背包在模板上只有j的遍历顺序不同，因此我们可以通过一个if语句来区分这两种背包，然后分别进行不同顺序的内层循环即可

• 然后其实01背包是一种特殊的多重背包，即01背包是数量上限为1的多重背包问题，这样一想其实就只用写多重背包的代码即可

3. 模板

int V, n, v[n], w[n], p[n], dp[maxv];  // p[i]表示每个物品的件数，-1代表无穷个

for (int i = 1; i <= n; i++)
    if (p[i] == -1)  // 完全背包
        for (int j = v[i]; j <= V; j++)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    else {
        for(int k = 1, num = min(p[i], V / v[i]); num > 0; k <<= 1) {  // 01背包和多重背包
            if(k > num) k = num;
            num -= k;
            for(int j = V; j >= k * v[i]; j --) {  // 01背包只会执行k=1这一次
                dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
            }
        }
    }

4. 例题

Luogu P1833 樱花
HDU 3535 AreYouBusy

五、二维背包问题

1. 定义

对于每件物品，具有两种不同的代价v[i], g[i]，选择这件物品必须同时付出这两种代价，对于每种代价都有一个可付出的最大值（背包容量）V, G，物品的价值为v[i]v[i]。问如何选择物品装入背包可使价值总和最大。

2. 解析

这个其实比较简单，就是让dp数组增加一维度即可。
即dp[i][j][k]表示前i件物品装入两种代价分别为j和k的背包时可获得的最大价值量。滚动数组后就变成dp[j][k]。直接看代码会就一目了然了。

3. 模板

int V, n, v[n], g[maxn], w[n], p[n], dp[maxv][maxg];  // v[i]和g[i]分别为两种代价
for (int i = 1; i <= n; i ++)
    for (int j = V; j >= v[i]; j --)
        for (int k = G; k >= g[i]; k --)
            dp[j][k] = max(dp[j][k], dp[j - v[i]][k - g[i]] + w[i]);

4. 例题

Luogu 1507 NASA的食物计划
HDU 2159 FATE

六、分组背包问题

1. 定义

有n件物品和一个容量为V的背包。第i件物品的体积是v[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。问如何选择物品装入背包可使价值总和最大。

2. 解析

其实分组背包可以把每个组看作一个物体，即这其实就是一个01背包问题，每个物体依然还是选和不选两种状态，只不过选的时候可以从组内的多个原物体种任意选一个。同样看代码就一目了然了。

3. 模板（伪代码）

for (所有的组k)
    for (int j = V; j >= 0; j--)
        for (所有属于组k的i)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i])

4. 例题

Luogu 1757 通天之分组背包
HDU 1712 ACboy needs your help

七、背包问题的其它要素

1. 问法不同

• 最大值、最小值： 一次对应max、min即可
• 方案数目：改为sum，同时注意初始化可能需要改变

2. 范围不同

• 最大化、最小化：
  初始化时对于前0个物品的价值量dp[i][0...V]全部初始化为0，这样即使最终的dp[n][V]未达到边界值也能有最值答案（根据提问内容不同可能会有所改变）

• 恰好装满
  初始化时dp[i][0]=0, dp[i][1...V]全部初始化为 -INF或INF，这样不能刚好达到V的方案的最终价值量就为 -INF或INF（根据提问内容不同可能会有所改变）

3. 打印路径

• 不使用滚动数组的写法，即有完整的dp[i][j]记录，然后通过递归的方法print_ans打印路径。这是我个人比较喜欢的写法，因为不用额外维护存储路径信息的数组😀

• 维护一个记录路径信息的数组
  记录下每个状态的最优值是由状态转移方程的哪一项推出来的。然后就可以根据这条记录找到上一个状态，从上一个状态接着向上推，得到整条路径。

3. 情景

区分背包问题是简单的，但是.....
如何才能发现一道题考察的是背包问题呢？
这就需要多刷题目，直到看到题目的某个情景就能反应出是在考察背包问题。

当然我还没到那种境界就是了hhh😀

参考博客：https://blog.csdn.net/yandaoqiusheng/article/details/84782655