动态规划之完全背包

前言

完全背包问题，相比 0/1背包问题，其实就是每个物品可以取无限次，就像“完全披萨”一样（无端联想）

一、完全背包𢖩莉典例

有 n(n ≤ 100) 种物品和一个容量为 m(m ≤ 10000) 的背包。第 i 种物品的容量是 c[i]，价值是 w[i]。

现在需要选择一些物品放入背包，每种物品可以无限选择，并且总容量不能超过背包容量，求能够达到的物品的最大总价值。

以上就是完全背包问题的完整描述，和 0/1 背包的区别单纯在于每种物品可以无限选取。

1、状态设计

状态(i, j)表示前i种物品恰好放入容量为j的背包 (0 ≤ i < n，0 ≤ j ≤ m)；

令 dp[i][j] 表示状态 (i, j) 下该背包得到的最大价值，即前i种物品（每种物品可以选择无限件）恰好放入容量为j的背包所得到的最大总价值；

2、状态转移方程

$dp[i][j]=max(dp[i-1][j-c[i] \times k]+w[i] \times k) \ \ (0 \le k \le \frac{j}{c[i]})$

因为每种物品有无限种可放置，将它归类为以下两种情况：

1）不放：如果 “第 i 种物品不放入容量为 j 的背包”，那么问题转化成求 “前 i-1 种物品放入容量为 j 的背包” 的问题；由于不放，所以最大价值就等于 “前 i-1 种物品放入容量为 j 的背包” 的最大价值，对应状态转移方程中 k = 0 的情况，即 dp[i-1][j]；

2）放 k 个：如果 “k个第 i 种物品放入容量为 j 的背包”，那么问题转化成求 “前 i-1 种物品放入容量为 j-c[i]*k 的背包” 的问题；那么此时最大价值就等于 “前 i-1 种物品放入容量为 j-c[i]*k 的背包” 的最大价值加上放入 k 个第 i 种物品的价值，即 dp[i-1][j - c[i]*k] + w[i]*k；

枚举所有满足条件的 k 就是我们所求的 “前 i 种物品恰好放入容量为 j 的背包” 的最大价值了。

3、对比 0/1 背包问题

完全背包问题是 0/1 背包问题的扩展，区别就是它可以选择取 0 件、取 1 件、取 2 件……取 k 件，而 0/1 背包问题只能取 0 件、取 1 件。如果从状态转移方程出发，我们可以把两个问题进行归纳统一，得到一个统一的状态转移方程如下：

$dp[i][j]=max(dp[i-1][j-c[i] \times k]+w[i] \times k)$

对于 0/1 背包问题，k 的取值为 0, 1；

对于完全背包问题，k 的取值为 0, 1, 2, 3, … , j/c[i]；

4、时间复杂度分析

对于n种物品放入一个容量为m的背包，状态数为 O(nm)，每次状态转移的消耗为 O(k)，所以整个状态转移的过程时间复杂度是大于O(nm)的，那么实际是多少呢？

考虑最坏情况下，即c[i] = 1时，那么要计算的 dp[i][j] 的转移数为 j，总的状态转移次数就是m(m+1)/2的，也就是说状态转移均摊时间复杂度是O(m)的。

这显然不够高效。有没有什么办法优化？

二、完全背包问题的优化

1、时间复杂度优化

我们把状态转移方程进行展开后得到如下的 k+1 个式子：

$dp[i][j]=max\left\{ \begin{array}{rcl} dp[i-1][j] & & {(1)}\\ dp[i-1][j-c[i]]+w[i] & & {(2)}\\ dp[i-1][j-c[i] \times 2]+w[i] \times 2 & & {(3)}\\…\\ dp[i-1][j-c[i] \times k]+w[i] \times k & & {(k+1)} \end{array} \right.$

利用待定系数法，用j-c[i]代替上式的j得到如下式子：

$dp[i][j-c[j]]=max\left\{ \begin{array}{rcl} dp[i-1][j-c[j]] & & {(1)}\\ dp[i-1][j-c[i] \times 2]+w[i] & & {(2)}\\ dp[i-1][j-c[i] \times 3]+w[i] \times 2 & & {(3)}\\…\\ dp[i-1][j-c[i] \times k]+w[i] \times (k-1) & & {(k)} \end{array} \right.$

等式两边都加上 w[i] 得到：

$dp[i][j-c[j]]+w[i]=max\left\{ \begin{array}{rcl} dp[i-1][j-c[j]]+w[i] & & {(1)}\\ dp[i-1][j-c[i] \times 2]+w[i] \times 2 & & {(2)}\\ dp[i-1][j-c[i] \times 3]+w[i] \times 3 & & {(3)}\\…\\ dp[i-1][j-c[i] \times k]+w[i] \times k & & {(k)} \end{array} \right.$

于是我们发现，这里的 (1)…(k) 式子等价于最开始的状态转移方程中的 (2) … (k+1) 式，所以原状态转移方程可以简化为：

$dp[i][j]=max(dp[i-1][j]+w[i],dp[i][j-c[i]]+w[i])$

这样就把原本均摊时间复杂度为O(m)的状态转移优化到了 O(1)。

那么我们来理解一下这个状态转移方程的含义：

对于第i种物品，其实只有两种选择：一个都不放、至少放一个；一个都不放就是 “前 i-1 种物品放满一个容量为 j 的背包” 的情况，即 dp[i-1][j]；至少放一个的话，我们尝试在 “前 i 种物品放满一个容量为 j 的背包” 里**拿掉 **1 个物品，即 “前 i 种物品放满一个容量为j-c[i]的背包”，这时候的值就是 dp[i][j-c[i]] + w[i]。取两者的大者就是答案了。

这也是完全背包问题的一种比较容易理解的思路。这也告诉我们，每一种"一眼丁真"成立的方法背后都是有严格推导支撑的。有些时候直觉并不靠谱，数学证明才是硬通货（）。

2、空间复杂度优化

因为当前行的状态的值只依赖于上一行和当前行的状态，和上上一行、上上上一行的状态无关，所以可以利用滚动数组记录上一行和当前行的状态，将上一行和当前行的状态进行滚动计算（自己去找啦，都已经能到这一步了，不要总是想着一篇文章解决，才不是因为我写了半天把自己绕晕了）。

根据优化后的状态转移方程，我们发现只需要保留一行状态，按照j递增进行顺序计算，就可以忽略i，做到把二维的问题转换成一维，将状态转移方程变成如下表示：

$dp[j]=max(dp[j],dp[j-c[i]]+w[i])$

肥肠的完美，直接把二维的问题转换成了一维的了。我们称之为高效（）。

三、练习时间！

面试题 08.11. 硬币 - 力扣（LeetCode）

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

经典老番嗷，谁还没有被这道题目折磨过的自觉去体验一把再回来。

(虽然这道题目不用动态规划也能写，不过我记得我当时用的是Python走的捷径……)

这道题的思路跟上面的基本一样，把有关条件替换掉就好了。~~（萝莉の至高力）~~

有 4 种物品和一个容量为 n 的背包。每种物品的容量分别是 25、10、5、1。

选择一些物品放入背包，每种物品可以无限选择，并且总容量不能超过背包容量，求有多少种装法。

话不多说，上代码！

int waysToChange(int n){ //成熟的人会自己脑补注释（实在不行交给GPT嘛）
	int dp[1000001];
    int b[] = {1, 5, 10, 25};
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for(int i = 0; i < 4; ++i) {
        for(int j = b[i]; j <= n; ++j) {
            dp[j] = (dp[j] + dp[j - b[i]]) % 1000000007;
        }
    }
    return dp[n];
}

322. 零钱兑换 - 力扣（LeetCode）

和上一题其实差不多，转换一下数组的定义就行了。

int coinChange(int* coins, int coinsSize, int amount) {
    int dp[10001];
    for(int i = 1; i < 10001; ++i) {
        dp[i] = 10000000;
    }
    dp[0] = 0;
    for(int i = 0; i < coinsSize; ++i) {
        for(int j = coins[i]; j <= amount; ++j) {
            if(dp[j - coins[i]] + 1 < dp[j]) {
                dp[j] = dp[j - coins[i]] + 1;
            }
        }
    }
    return dp[amount] == 10000000 ? -1 : dp[amount];
}