代码随想录算法训练营DAY42|C++动态规划Part4|0-1背包理论基础(一)、0-1背包理论基础之滚动数组（二）、416.分割等和子集

0-1背包理论基础(一)

卡码网第46题

文章讲解：0-1背包理论基础(一)

视频讲解：带你学透0-1背包问题！

背包问题经典资料：背包九讲。卡哥文章里说：“对于面试的话，其实掌握01背包，和完全背包，就够用了，最多可以再来一个多重背包。”

前置知识

背包问题的各种分类：

在笔试面试中，基本搞清楚01背包和完全背包即可，在后续的文章中会简单讨论多重背包问题。

其中，完全背包问题从图中也可以看出，是由01背包问题演化而来。

01背包

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

首先我们思考用暴力解法：

每一个物品只有两种状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是$o(2^n)$，这里的n表示物品数量。

动态规划：01背包

假设背包最大重量是4，即 bagweight = 4

并在下文的叙述中，背包当前允许重量表示当前背包最高允许的重量(可能是0,1,2,3,4)，背包容量表示背包的最大重量4

二维dp数组

在后文中，我们会介绍一维dp数组的解法

• 确定dp数组以及下标的含义

对于背包问题，有一种写法， 是使用二维数组，即**dp[i][j] 表示从下标为[0-i]的物品里任意取，放进当前允许重量为j的背包(j <= bagweight)，价值总和最大是多少**。

可视化：

• 确定递推公式

  思考一下，我们可以从那两个方向推导出来dp[i][j]呢？（注意：物品只有1个，放完就没有了喔）

  • 一个是从上面格子[i-1][j]推导下面格子[i][j]——放不下物品i
    • 由dp[i - 1][j]推出，即背包当前允许重量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的当前允许重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
  • 一个是从左上角的某个格子推导出[i][j]格子——能放下物品i
    • 由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

  综上所述有两个递推公式：

  满足 j < weight[i]时，意味着放不下i：dp[i][j]=dp[i-1][j]

  满足j >= weight[i]时：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

• dp数组输入初始化

  关于初始化，一定要和dp数组的定义温和，否组到递推公式的时候就会越来越乱

  1. 首先可以敲定，如果背包容量j为0的话，背包价值总和一定是0:

2. 如果背包容量j < weight[0]，也就是说背包根本装不下物品0，那么dp[0][j]当然也全部都是0；
3. 如果背包 j >= weight[0]，那么就是说背包能把物品零装下了，则初始化为dp[0][j]，其值为value[0]。

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

初始化完成后，结果为：

剩下的格子，初始化为多少都无所谓，因为剩下的格子应该是在运行时推导填写出来的，这里为了处理方便，先初始化为0。总体的初始化代码如下：

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

• 确定遍历顺序

  • 无论是先遍历物品还是先遍历背包重量，都是可以的。

  // 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]);
      }
  }
  

• 举例推导dp数组

做动态规划的题目，最好的过程就是自己在纸上举一个例子把对应的dp数组的数值推导一下，然后在动手写代码！

CPP代码

//二维dp数组实现
#include <bits/stdc++.h>
using namespace std;

int n, bagweight;// bagweight代表行李箱空间
void solve() {
    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 = 1; j <= bagweight; j++) { // 遍历行李箱容量
            // 如果装不下这个物品,那么就继承dp[i - 1][j]的值
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            // 如果能装下,就将值更新为 不装这个物品的最大值 和 装这个物品的最大值 中的 最大值
            // 装这个物品的最大值由容量为j - weight[i]的包任意放入序号为[0, i - 1]的最大值 + 该物品的价值构成
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }
    cout << dp[weight.size() - 1][bagweight] << endl;
}

int main() {
    while(cin >> n >> bagweight) {
        solve();
    }
    return 0;
}

再论01背包的遍历顺序

之前我们说，无论先遍历背包容量还是先遍历物品都是可以的，这是为什么呢？

其实简单思考一下就知道了，从图形上来说：

如果是从左到右去填值（先遍历物品），我们[i][j]位置只由上方和左上角某值决定，所以合理！

如果从上到下去填值（先遍历背包），我们仍然能先完成[i][j]位置上方和左上角某值的填充，非常合理！

0-1背包理论基础(二)

卡码网第46题

文章讲解：0-1背包理论基础(二)

视频讲解：带你学透0-1背包问题！（滚动数组）

还记得我们在[再论01背包的遍历顺序](# 再论01背包的遍历顺序)讨论的遍历顺序吗，我们发现一个很关键的点，那就是本次状态（第[i]层）只与其整个上一层的状态（第[i-1]层）有关，所以我们其实很容易想到，如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);。还能再优化吗？与其把上一层的状态拷贝到本层上，我们不如只用一个一维数组，也就是dp[j]。这是状态的压缩，也就是滚动数组的由来。

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

滚动数组需要满足：需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

下面我们直接从dp数组的初始化开始讲起：

一维dp数组如何初始化

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j].

那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。

vector<int> dp(n + 1, 0);

一维dp数组遍历顺序

在讲遍历顺序之前，我想再谈一次为什么本题可以用一维数组来遍历：

因为我们对每一个格子本质上还是需要依靠上一层格子来计算出本格子的值（这一句话看不懂可以再次阅读[0-1背包理论基础(一)](# 0-1背包理论基础(一))中谈到的递推和遍历思想）。

只不过我们把上一个层的值保存到了一维数组中，我们是依靠已有的数组的值/来进行/待计算值的/更新。

通过块中的文字，我们就可以知道，本题是不能先遍历背包容量，再遍历物品的，因为在二维世界中，这种遍历方法是从上到下的，本格子的值依赖上一层左上角的值，这样我们在一维数组中无法保存上一层的状态。（如果不明白，待会可以自己试一试就知道了）

揭晓答案了！一维dp的遍历顺序只能是先物品，再背包！

并且本题中的背包只能逆序遍历，也就是从大到小遍历，知道减小到当前材料所占的空间，为什么从大到小遍历呢？

之前谈到我们本质上还是在遍历一个二维数组，只不过我们在不停得对其进行更新，如果从小到大遍历，我们就会覆盖掉上一层的值，导致之前状态的丢失！所以从大到小遍历，完美利用上一层左上角格子和上层格子的状态！

举例推导dp数组

还是用上一题中的例子

CPP代码

// 一维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;
}

416.分割等和子集

力扣题目链接

文章讲解：416.分割等和子集

视频讲解：动态规划之背包问题，这个包能装满吗？| LeetCode：416.分割等和子集

状态：如何把他抽象成一个背包问题呢？一脸懵逼
看了如何抽象成背包问题后建议直接开始做，很舒服

没有抓住题目的重点，题目是要求分割等和子集，规定的分割方式是吧给定集合分割成两个集合，两个子集合的值相等。

那么整个集合的和除以2，其实就是每个子集合的和。那么首先要求想到回溯算法，这里不加论述，因为回溯算法会超时，这里主要讲将本题抽象成一个01背包问题。

思路

本题的本质就是，选取集合中元素，看有哪些元素相加能够等于 sum(nums) / 2。

这里举一个具体的例子 ，给定nums = [1, 5, 11, 5]，数组元素和为22，现在我们要分隔两个等和子集，也就是要求每个子集和为11。所以我们需要从 nums里面选一些元素，使其和为11。那么剩下的元素肯定也是11。

现在你能将本题抽象成一个背包问题吗？

将题目抽象成0-1背包问题

我们吧nums中的元素抽象成每个物品的重量，同时也是价值，然后要求的子集合之和11为背包容量。由于我们每个元素只能用一次，所以这不就是明显的01背包问题。

这里我们更加具体一点：

• 背包的体积为sum / 2
• 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为 元素的数值
• 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
• 背包中每一个元素是不可重复放入

综上所述，我们开始用01背包套用本题！（用一维数组来讨论）

1. 确定dp数组以及下标的含义：

dp[j]表示容量为j的背包，所背的物品价值最大可以为dp[j]。

2. 确定递推公式

跟之前一样，递推公式为: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数组如何初始化

跟之前一样dp[0]初始化为0，在一个本题的价值都是正整数，所以非0下标也是初始化为0

如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

vector<int> dp(10001, 0);

4. 确定遍历顺序

如果使用一维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]);
    }
}

5. 举例推导dp数组

   如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。

CPP代码

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;
    }
};