《代码随想录第三十九天》——背包问题二维、背包问题一维、分割等和子集

《代码随想录第三十九天》——背包问题二维、背包问题一维、分割等和子集

本篇文章的所有内容仅基于C++撰写。

1. 背包问题二维

背包问题掌握01背包和完全背包即可，多重背包都比较少。
而完全背包又是也是01背包稍作变化而来，即：完全背包的物品数量是无限的。所以背包问题的理论基础重中之重是01背包，一定要理解透！

1.1 题目

携带研究材料

• 01背包问题：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

假设背包最大重量为4。
物品为：
重量 价值
物品0 1 15
物品1 3 20
物品2 4 30
问背包能背的物品最大价值是多少？

1.2 分析

1. 确定dp数组以及下标的含义
   需要使用二维数组，因为有两个维度需要分别表示：物品 和 背包容量，即二维数组为 dp[i][j]。其中i表示第几个物品，j表示背包容量，而dp[i][j]表示在当前背包容量放入的物品价值（具体价值根据题目而定，可以是截止i的某一个物品的价值，也可以是截止i的多个物品价值之和，此处要求最大价值，因此尽量在背包容量允许的情况下放入更高价值的一个或多个物品）。

2. 确定递推公式
   对于递推公式，首先我们要明确有哪些方向可以推导出 dp[i][j]。
   这里我们dp[1][4]的状态来举例：
   求取 dp[1][4] 有两种情况：

• 放物品1
• 不放物品1
  如果不放物品1， 那么背包的价值应该是 dp[0][4] 即 容量为4的背包，只放物品0的情况。
  推导方向如图：
  
  如果放物品1， 那么背包要先减掉物品1所需的容量，目前容量是4，物品1 的容量为3，此时背包剩下容量为1。由于01背包的物品不能重复放，因而此时背包只能装物品1的上一排，即物品0处容量为1的值。所以 放物品1 的情况 = dp[0][1] + 物品1 的价值，推导方向如图：
  
  两种情况，分别是放物品1 和 不放物品1，我们要取最大值（毕竟求的是最大价值）：dp[1][4] = max(dp[0][4], dp[0][1] + 物品1 的价值)

以上过程抽象化如下：

• 不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]。
• 放物品i：背包空出物品i的容量后，背包容量为j - weight[i]，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

因此递归公式为： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. dp数组如何初始化
   关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。如图：
   
   而由于物品0在背包每个容量中装的情况无法根据递推公式得出，所以也需要初始化。注意，只需要把背包容量>=物品0重量的情况初始化，因为这些情况下背包才能装下物品。

for (int i = 1; i < weight.size(); i++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
    dp[i][0] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

如果我们预先把整个数组初始化为0：

vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

4. 确定遍历顺序
   那么问题来了，先遍历 物品还是先遍历背包重量呢？其实都可以！！ 但是先遍历物品更好理解。

先遍历物品：

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

先遍历背包：

// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

1.3 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, bagweight;// bagweight代表行李箱空间

    cin >> n >> bagweight;

    vector<int> weight(n, 0); // 存储每件物品所占空间
    vector<int> value(n, 0);  // 存储每件物品价值

    for(int i = 0; i < n; ++i) {
        cin >> weight[i];
    }
    for(int j = 0; j < n; ++j) {
        cin >> value[j];
    }
    // dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

    // 初始化, 因为需要用到dp[i - 1]的值
    // j < weight[0]已在上方被初始化为0
    // j >= weight[0]的值就初始化为value[0]
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }

    for(int i = 1; i < weight.size(); i++) { // 遍历科研物品
        for(int j = 0; j <= bagweight; j++) { // 遍历行李箱容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 如果装不下这个物品,那么就继承dp[i - 1][j]的值
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }
        }
    }
    cout << dp[n - 1][bagweight] << endl;

    return 0;
}

2. 背包问题一维

2.1 题目

本题链接与上题相同：
携带研究材料

• 题目描述
  小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。
  小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

• 输入描述
  第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。
  第二行包含 M 个正整数，代表每种研究材料的所占空间。
  第三行包含 M 个正整数，代表每种研究材料的价值。

• 输出描述
  输出一个整数，代表小明能够携带的研究材料的最大价值。
  输入示例
  6 1
  2 2 3 1 5 2
  2 3 1 5 4 3
  输出示例
  5

• 提示信息
  小明能够携带 6 种研究材料，但是行李空间只有 1，而占用空间为 1 的研究材料价值为 5，所以最终答案输出 5。
  数据范围：
  1 <= N <= 5000
  1 <= M <= 5000
  研究材料占用空间和价值都小于等于 1000

2.2 分析

一维数组可以看成是物品行重叠的二维数组，它的优势在于可以减小内存空间的占用。

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。

动规五部曲分析如下：

1. 确定dp数组的定义
   在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

2. 一维dp数组的递推公式
   二维dp数组的递推公式为： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
   所以一维数组的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

其中，dp[j]为 容量为j的背包所背的最大价值。dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。dp[j - weight[i]] + value[i] 表示 容量为 [j - 物品i重量] 的背包 加上 物品i的价值。此时dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，需要求最大价值

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3. 一维dp数组如何初始化
   dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。
   那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？如果题目给的价值都是正整数，那么非0下标都初始化为0就可以了。
   这跟二维数组不一样，没有i-1的情况，所以物品0的每一行都初始化为0就可以，因为循环的过程中会把它装进背包。

4. 一维dp数组遍历顺序
   代码如下：

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

这里大家发现和二维dp的写法中，遍历背包的顺序是不一样的！二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。原因在于，虽然变成了一维数组，但本质上当前位置还是会从“左上侧”和“上侧”取值，如果从前向后计算的话，那么前面的值被更新后又参与计算，导致同样的物品被多次加入背包。所以应该保证前面的值是”上一排”的值，这样从后面向前更新不会破坏原有的状况。

2.3 代码

// 一维dp数组实现
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 读取 M 和 N
    int M, N;
    cin >> M >> N;

    vector<int> costs(M);
    vector<int> values(M);

    for (int i = 0; i < M; i++) {
        cin >> costs[i];
    }
    for (int j = 0; j < M; j++) {
        cin >> values[j];
    }

    // 创建一个动态规划数组dp，初始值为0
    vector<int> dp(N + 1, 0);

    // 外层循环遍历每个类型的研究材料
    for (int i = 0; i < M; ++i) {
        // 内层循环从 N 空间逐渐减少到当前研究材料所占空间
        for (int j = N; j >= costs[i]; --j) {
            // 考虑当前研究材料选择和不选择的情况，选择最大值
            dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);
        }
    }

    // 输出dp[N]，即在给定 N 行李空间可以携带的研究材料最大价值
    cout << dp[N] << endl;

    return 0;
}

3. 分割等和子集

3.1 题目

分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100

3.2 分析

这道题要灵机一动，把它转换成背包问题。要分割两个等和子集，也就是set1 = set2 = sum/2。也就说明可以从中挑选任意个数字（假设为x），将其放入容量大小为sum/2的背包中。如果这x个数刚好能把sum/2的背包装满，说明剩下的(n-x)个数也就等于sum/2，即能找到两个相等子集。
动规五部曲分析如下：

1. 确定dp数组以及下标的含义
   01背包中，dp[j] 表示： 容量（所能装的重量）为j的背包，所背的物品价值最大可以为dp[j]。
   如果背包所载重量为target， dp[target]就是装满 背包之后的总价值，因为 本题中每一个元素的数值既是重量，也是价值，所以，当 dp[target] == target 的时候，背包就装满了。

2. 确定递推公式
   01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
   本题相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]，所以递推公式：
   dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

3. dp数组如何初始化
   在01背包，一维dp如何初始化，已经讲过，从dp[j]的定义来看，首先dp[0]一定是0。
   如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。这样才能让dp数组在递推的过程中取得最大的价值，而不是被初始值覆盖。

• 本题题目中 只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。

vector<int> dp(10001, 0);

4. 确定遍历顺序
   在动态规划：关于01背包问题，你该了解这些！（滚动数组） (opens new window)中就已经说明：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！

// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}

3.3 代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;

        // dp[i]中的i表示背包内总和
        // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
        // 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
        vector<int> dp(10001, 0);
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        // 也可以使用库函数一步求和
        // int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 == 1) return false;
        int target = sum / 2;

        // 开始 01背包
        for(int i = 0; i < nums.size(); i++) {
            for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        // 集合中的元素正好可以凑成总和target
        if (dp[target] == target) return true;
        return false;
    }
};

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)，虽然dp数组大小为一个常数，但是大常数