代码随想录算法训练营打卡Day44 | 完全背包问题、LeetCode518 零钱兑换II、LeetCode377 组合总和IV

摘要

只需改变递推公式的一处，就可以将 0-1 背包问题变为完全背包问题。
使用滚动数组时，0-1 背包倒序遍历重量的维度，保证每件物品最多被选取一次；而完全背包正序遍历重量的维度，让每种物品可以被选取多次。
先遍历物品，再遍历背包，求的是组合数。先遍历背包，再遍历物品，求的是排列数。如果只是要解决背包装入物品的价值，或者尽可能装满背包能装多少等不关心具体选取物品方案的问题，也就不需要关心先遍历物品还是先遍历背包。

完全背包问题

有 n 种物品和一个最多能背重量为 w 的背包。第 i 种物品的重量是 weight[i]，得到的价值是value[i] 。每种物品可以选取多件，求解将哪些物品装入背包里物品价值总和最大。

完全背包问题和 0-1 背包问题唯一的不同之处：每种物品可以被多次选取。
确定dp数组及数组下标的含义，先从二维的dp数组开始。
- 在第0种物品到第i种物品中任取物品（每种物品可以被多次选取），放进容量为j的背包中，能获得的最大价值为dp[i][j]。
- dp[i][j]有两种可能：
  1. 不放第i种物品，或者说：一件第i种物品都放不下了，而且一件第i种物品替换已经放入的任何物品都不会使得背包内物品得总价值更大。那么 $dp[i][j]=dp[i-1][j]$
  2. 放第i种物品，放几件不知道，假设放入k件第i种物品，那么可以得到 $dp[i][j]=dp[i][j-k*weight[i]]+k*value[i]$ 。当然，实现代码中不会这样写，也很难写出来，因为这样表示放入第i种物品并没有把状态划分清楚，还有更好的表示方法。如何控制这个k的取值呢？把状态划分清楚，并不需要显式地去控制这个k。
假设要尝试放入一件第i种物品，把放入第i种物品看成是一件一件放的过程，那么
1. 不放第i种物品： $dp[i][j]=dp[i-1][j]$
2. 只放一件第i种物品，这就和 0-1 背包问题没什么区别，之前并没有放过第i种物品，所以dp[i][j]可以看作由之前在第0种到第i-1种物品任取之后再放入一件第i种物品得到。 $dp[i][j]=max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])$ 。但现在是完全背包问题，怎么会和 0-1 背包一样呢？再放一件第i种物品试试。
3. 再放一件第i种物品：。因为每种物品是多次选取的，可以将完全背包问题的dp[i][j]看成是由在第0种到第i种物品中任选物品得到的。
  - 仍然是要尝试放一件第i种物品，但是之前可能已经放过了第i种物品，所以dp[i][j]并不一定是由之前在第0种到第i-1种物品任取之后再放入一件第i种物品得到的。如果写成 $dp[i][j]=dp[i-1][j-weight[i]]+value[i]$ ，那就没有考虑到之前已经放入了第i种物品的情况，就不符合完全背包问题的规则了，也不符合我们对dp数组的定义。
  - $dp[i][j]=dp[i][j - weight[i]]+value[i]$ ，说明尝试再放一件第i种物品，之前的状态是在第0种到第i种物品中任选物品得到的，这包含了之前放过第i种物品和之前没有放过第i种物品。
这里就体现出完全背包问题和 0-1 背包问题的不同之处
- 0-1 背包问题： $dp[i][j]=max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])$
- 完全背包问题： $dp[i][j]=max(dp[i-1][j], dp[i][j-weight[i]]+value[i])$
从数学上也可以看出，完全背包问题的dp[i][j]是可以通过dp[i][j-weight[i]]来累加weight[i]的，这就达到了控制放入k件第i种物品的目的。
分析了原始的二维dp数组，接下来要使用滚动数组来简化代码和节省空间。
- dp[j]表示，从第0种物品到第i种物品中任取，物品的重量总和不超过j，所能得到的最大价值为dp[j]。
- 在代码随想录算法训练营打卡Day42中，分析了 0-1 背包问题中使用滚动数组时，重量这个维度为什么要倒序遍历，即j从大到小遍历dp数组，这符合递推公式中状态更新的依赖关系和先后顺序，也保证了每个物品最多只能使用一次。
- 而在完全背包问题中，j应该从小到大遍历dp数组。从递推公式上看，由于第i种物品是一件一件尝试放入的，dp[i][j]和dp[i][j-weight[i]]明显在二维dp数组的同一行，而dp[i][j-weight[i]]在dp[i][j]的左边。这说明要从左到右来更新dp数组，要用这一行的“新的”dp[j-weight[i]]来更新dp[j]，这样才符合dp数组的含义和递推公式，而不能用上一行的"旧的"dp[j-weight[i]]。

测试代码如下

// CompleteBag.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
using namespace std;

class testcase {
public:
    vector<int> weight;
    vector<int> value;
    int maxWeight;
    testcase(const vector<int> weight, const vector<int>& value, int maxWeight) {
        this->weight = weight;
        this->value = value;
        this->maxWeight = maxWeight;
    }

    int testCompleteBag_2dp() {
        vector<vector<int>> dp(weight.size(), vector<int>(maxWeight + 1, 0));

        // 初始化
        for (int j = 0; j <= maxWeight; j++) {
            if (j - weight[0] >= 0)
                dp[0][j] = max(dp[0][j], value[0] + dp[0][j - weight[0]]);
        }

        // 更新dp数组
        for (int i = 1; i < value.size(); i++) {
            for (int j = 0; j <= maxWeight; j++) {
                if (j - weight[i] >= 0)
                    dp[i][j] = max(dp[i - 1][j], value[i] + dp[i][j - weight[i]]);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }

        return dp[weight.size() - 1][maxWeight];
    }

    int testCompleteBag_1dp() {
        vector<int> dp(maxWeight + 1, 0);

        // 更新dp数组
        for (int i = 0; i < weight.size(); i++) {
            for (int j = 0; j <= maxWeight; j++) {
                if (j >= weight[i]) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }

        return dp[maxWeight];
    }

};

int main()
{
    testcase t1({ 1, 3, 4 }, { 15, 20, 30 }, 4);
    cout << t1.testCompleteBag_2dp() << endl;
    cout << t1.testCompleteBag_1dp() << endl;
}

LeetCode518 零钱兑换

518. 零钱兑换 II - 力扣（Leetcode）

这道题目要求的是装满背包有多少种方法，而且每种零钱能多次选取，所以是完全背包问题。
确定dp数组及数组下标的含义：dp[j]为用第0种到第i种零钱，凑成金额j的方法种数。从第0种到第i种零钱，每遍历到一种零钱，dp[j]更新一轮。
确定递推公式，先看简单的子问题：
- dp[0]，不放零钱，金额为0，就一种方法，dp[0]=1
- dp[1]，只能放入金额为1的零钱，如果不能选金额为1的零钱，就是0种方法，如果可以选金额为1的零钱，就是1种方法。
- dp[j]，假设现在要尝试放入金额为coins[i]的零钱。那么为了凑成总金额j，还要放入金额为j - coins[i]的零钱，而根据dp数组的定义，放入金额为j - coins[i]的零钱的方法就是dp[j - coins[i]]。由于还有其他可能的零钱组合得到总金额j，所以dp[j-coins[i]]是“新增”的方法数。
$dp[j] = dp[j] + dp[j - coins[i]]$
根据上述分析，dp数组的初始状态就是dp[0]=1，其他的dp[j]=1
遍历顺序，完全背包问题，每种零钱可以重复使用，所以j应该从小到大遍历。

接下来用 $LeetCode$ 的示例 $1$ 演示 dp数组的更新过程。

image.png

先初始化dp数组

从左到右逐个格子向下滑动，当j < coins[i]时，“新的”dp[j]就等于上一行的dp[j]。先滑动dp[0]。

coins[0]=1，所以dp[1]=dp[1]+dp[0]。

逐个格子滑动完一行

逐行滑动，完成dp数组的更新。

题解代码如下

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);

        dp[0] = 1;
        for (int i = 0; i < coins.size(); i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }

        return dp[amount];
    }
};

先遍历物品，在遍历背包，则物品放入背包（放入集合）中的顺序就是原来在输入数组中的顺序。物品放入的顺序是固定的，不会出现其他顺序。例如本题遍历到coins[1]=2要更新dp[3]时，只会新增 {1，2} 这种情况，不会新增 {2，1} 这种情况，因为coins[0]=1已经在外层循环遍历完了，之后的循环没有办法再“放入coins[0]=1”。所以，先遍历物品，再遍历背包，求的是组合数。
先遍历背包，再遍历物品，求的是排列数，先看下一题。

先遍历物品，在遍历背包，则物品放入背包（放入集合）中的顺序就是原来在输入数组中的顺序。物品放入的顺序是固定的，不会出现其他顺序。例如本题遍历到coins[1]=2要更新dp[3]时，只会新增 {1，2} 这种情况，不会新增 {2，1} 这种情况，因为coins[0]=1已经在外层循环遍历完了，之后的循环没有办法再“放入coins[0]=1”。所以，先遍历物品，再遍历背包，求的是组合数。
先遍历背包，再遍历物品，求的是排列数，先看下一题。

LeetCode377 组合总和IV

377. 组合总和 Ⅳ - 力扣（Leetcode）

这道题目和上一题类似，区别在于题目明显地提示我们答案要求的是排列数。

dp数组及数组下标的含义是相同的；递推公式和初始化也是相同的。dp[j]表示求总和为target的元素组合的个数，遍历到nums[i]时， $dp[j] = dp[j] + dp[j - nums[i]]$ 。这部分就略过了。
先遍历背包，再遍历物品，外层循环是背包容量，内层循环是物品，遍历物品要遍历target轮，元素的顺序是不受限制的。例如，对于nums = [1,2,3]，上一轮放入了一个nums[1]=2，这一轮还是从nums[0]开始，所以可以得到 {2, 1} 这种情况。既然元素的放入背包的顺序不受限制，换句话说就是，一组相同的元素按不同的放入顺序会被当成不同的方法。所以，先遍历背包，再遍历物品，得到的是组合数。

题解代码如下

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;

        for (int j = 0; j <= target; j++) {
            for (int i = 0; i < nums.size(); i++) {
                // LeetCode 的测试数据会造成 int 溢出，而且数值很大，不能用位数更多的整形处理
                // 而题目明确说了 target 不超过 int 的最大值，所以这部分溢出的 dp 数组可以不计算，看作和答案无关
                if (j - nums[i] >= 0 && dp[j] >= INT_MAX - dp[j - nums[i]]) 
                    continue;
                if (j - nums[i] >= 0) dp[j] += dp[j - nums[i]];
            }
        }

        return dp[target];
    }
};

那求排列数和求组合数到底有什么不同？以上述示例nums = [1,2,3]; target = 4为例，手动推导一下dp数组的更新过程。两个箭头的终点指向同一个格子，表示两个箭头起点的数字相加。

初始化dp数组

先遍历j，再遍历i，这个窗口可不是逐行向下滑动的了，而是从左到右每个格子依次直接滑动到底，每个dp[j]都枚举了一次nums中的所有物品，这就给求排列数提供了便利。那么先滑动dp[0]，如下图。

同理，dp[1]也应直接滑动到底。dp[1]的更新如下图所示

dp[2]的更新如下图所示

dp[3]的更新

dp[4]的更新，得到答案

可见，如果先遍历背包（遍历j），再遍历物品（遍历i），从二维数组来看，dp[j]更新依赖的值就是已经遍历了所有物品的dp[j-1]，也就是最后一行的dp[j-1]。
由于每个dp[j]都遍历了一轮所有物品，所以物品放入背包的先后顺序不会被物品在输入数组中的顺序固定，可以求出排列的种数。
也可以这么理解，
- dp[j]先遍历了一遍所有种类的物品，相当于对于j这块容量，我们对所有种类的物品都进行了一次放入背包的尝试。
- 对于每一块j这么大的容量，都对所有种类的物品进行了一次放入背包的尝试，自然能尝试出元素总和为target的排列。或许动态规划在求排列数时是一种更高明的枚举法。

代码随想录算法训练营打卡Day44 | 完全背包问题、LeetCode518 零钱兑换II、LeetCode377 组合总和IV

代码随想录算法训练营打卡Day44 | 完全背包问题、LeetCode518 零钱兑换II、LeetCode377 组合总和IV

摘要

完全背包问题

LeetCode518 零钱兑换

LeetCode377 组合总和IV

相关阅读更多精彩内容

友情链接更多精彩内容