代码随想录算法训练营打卡Day42 | 0-1 背包问题、LeetCode416 分割等和子集

摘要

0-1 背包问题是动态规划的经典问题，通过“缩小”背包来找到问题的简单的子结构，再“放大”背包，用子结构来推导答案。
推导dp[i][j]所需的状态不一定在二维dp数组中与dp[i][j]相邻（dp[i][j]=max(dp[i-1][j], value[i]+dp[i-1][j-weight[i]])），其中dp[i-1][j-weight[i]]在二维dp数组中不一定与dp[i][j]相邻。这从侧面反映了 0-1 背包问题与较简单的动态规划问题的不同之处， 0-1 背包的状态转移更难理解，而较简单的动态规划的题目往往只在相邻的状态间转移。
在使用滚动数组优化空间复杂度前，要明确保存在滚动数组中的状态的更新的先后顺序，状态的更新顺序要符合递推公式的含义。

0-1 背包问题（二维dp）

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

dp数组及数组下标的含义：在第0号物品到第i号物品中任取物品（每件物品要么取一次，要么不取），放进容量为j的背包中，能获得的最大价值为dp[i][j]。
确定状态转移方程，还是先看简单的子问题
- 只讨论放不放第0号物品，当然是放0号物品进入背包中能获得最大价值，但还要看第0号物品能不能放入背包中，所以可以得到： $dp[0][j]=\begin{cases} 0, & j < weight[0] \\ value[0], & j \ge weight[0] \end{cases}$
- 再看从第0号到第i号中选物品来放，假设我们已经知道从第0号到第i-1号怎么取放入容量为j的背包得到的价值最大（即dp[i-1][j]已知），那么dp[i][j]有两种可能：
  1. 不放第i号物品，或者说：第i号物品放不下了，而且第i号物品替换已经放入的任何物品都不会使得背包内物品得总价值更大。那么dp[i][j]=dp[i-1][j]
  2. 放第i号物品，为了保证能放入第i号物品，要先给它腾出足够的容量weight[i]，再用剩下的容量j-weight[i]去找从第0号到第i-1号物品中取得最大价值的取法。那么dp[i][j]=values[i]+dp[i-1][j-weight[i]]。
- 到这里可以尝试写出状态转移方程：
  $dp[i][j]= \begin{cases} 0, & j < \underset{0 \le k \le i}{min}(weight[k]) \\ values[k], & j = \underset{0 \le k \le i}{min}(weight[k]) \\ max(dp[i-1][j], values[i]+dp[i][j-weight[i]]), & else \end{cases}$
根据状态转移方程，可以知道如何初始化dp数组
- 对于dp数组下标为0的行：当j小于第0号物品的重量时，dp[0][j]=0;当j不小于第0号物品的重量时，dp[0][j]=values[0]。
- 对于dp数组下标为0的列：当j为0时，不能放入任何物品，所以dp[i][0]=0。
- 对于行下标非零或列下标非零的dp数组的元素，由于dp[i][j]都是由之前已知的两种状态的其中一种推导出来的，所以可以初始化成任意值，C++数组（array或vector）不显式初始化时默认初始化为0。
接下来以maxWeight=4; weight={1, 3, 4}; values={15, 20, 30};为例，演示dp数组的初始化和推导过程。

背包的最大重量为4

物品对应的下标	重量	价值
0	1	15
1	3	20
2	4	30

dp数组的初始化

接下来要确定遍历dp数组的方法，先看dp[i][j]与dp[i-1][j]的位置关系，再看dp[i][j]与dp[i-1][j-weight[i]]的位置关系，如下图。dp[i-1][j]和dp[i-1][j-weight[i]]都在dp[i][j]的上一行，先遍历行后遍历列是可以的；dp[i-1][j]和dp[i][j]在同一列，和dp[i-1][j-weight[i]]在dp[i][j]左边的列中，所以先列后行也是可以的。

把dp数组推导完

可以得到答案为35。

LeetCode 上没有直接的0-1背包问题，所以只能在本地环境下测试实现代码

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

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

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

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

        // 初始化
        for (int j = 0; j <= maxWeight; j++)
            dp[0][j] = j <= weight[0] ? value[0] : 0;

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

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

};

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

0-1 背包问题（滚动数组，一维dp）

0-1 背包问题可以用滚动数组来优化空间复杂度，可以用在二维dp数组上的滑动窗口来理解滚动数组。dp[j]的含义是，容量为j的背包能装入的最大价值，dp[j]的更新次数对应着可选取的物品范围，即dp[j]更新了i次时，表示的就是原来的dp[i][j]。
还是以maxWeight=4; weight={1, 3, 4}; values={15, 20, 30};为例；青蓝色的格子表示当前dp[j]中保存的值

初始化dp数组

接下来要逐个格子往下滑动这个窗口了，怎么滑动呢？是从左到右滑动还是从右到左滑动呢？j是从小到大还是从大到小呢？
- 在 62. 不同路径 - 力扣（Leetcode）中，我们是从左到右逐个格子滑动这个窗口的（代码随想录算法训练营打卡Day39 ）。因为dp[j]的更新不仅依赖上一行的状态（“旧的”dp[j]，表示从上面一格向下走到达本格），也依赖同一行的状态（新的dp[j-1]，表示从左边一格向右走到达本格）。要更新dp[j]，就要先更新dp[j-1]，所以要从左到右逐个格子滑动这个窗口。
- 但是在 0-1 背包问题中，dp[j]的更新依赖的状态都是上一行的状态：一是"旧的"dp[j]，二是“旧的”dp[j-nums[i]]。所以我们选择要选择一种不会提前覆盖dp[j]更新依赖的状态的遍历顺序。而dp[j-nums[i]]在dp[j]的左边，要让dp[j-nums[i]]不被提前覆盖，应该以从右到左，即j从大到小的顺序来更新dp[j]
所以，我们先更新dp[4]，dp[4]向下滑动一格，从图中也可以看出dp[4 - weight[1]]确实还在上一行，不会被提前覆盖。

然后从右到左逐个格子向下滑动，注意到j < weight[i]时，“新的”dp[j]就等于“旧的”dp[j]。

测试代码如下

// 01bag.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 test01bag_2dp() {
        vector<vector<int>> dp(weight.size(), vector<int>(maxWeight + 1, 0));

        // 初始化
        for (int j = 0; j <= maxWeight; j++)
            dp[0][j] = j <= weight[0] ? value[0] : 0;

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

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

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

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

        // 更新dp数组
        for (int i = 1; i < weight.size(); i++) {
            for (int j = maxWeight; j >= weight[i]; j--) {
                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.test01bag_2dp() << endl;
    cout << t1.test01bag_1dp() << endl;
}

运行结果截图

LeetCode416 分割等和子集

416. 分割等和子集 - 力扣（Leetcode）

这道题目可以用回溯法解决，但回溯法的时间复杂度一般为O(2^n)；对于这道题，动态规划是更好的解法，这道题目可以转化成 0-1 背包问题。
转化成背包问题，首先要明确什么是物品，什么是背包，以及三个参数
1. 各个物品的 value
2. 各个物品的 weight
3. 背包的最大容量
nums中的每个数字都是物品，设nums中每个数字的和为sum，背包容量为sum / 2。第i个数字的value是nums[i]，weight也是nums[i]。
明确dp数组及下标的含义：dp[j]表示从nums中选取数字得到的和不大于dp[j]的最大值。
这样就保证了如果从nums中取出一个子集，其要么等于dp[sum/2]，要么小于dp[sum/2]。
如果dp[sum/2]==sum/2，就说明我们能找到一个合适的子集，使得这个子集的和等于sum/2，此时另一个子集的和也是sum/2。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (auto& iter : nums) sum += iter;
        if (sum % 2) return false;
        
        int target = sum / 2;
        vector<int> dp(target + 1, 0);
        
        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]);
            }
        }

        return dp[target] == target;
    }
};