【动态规划专栏】– 01 背包问题 — 动态规划经典题型

目录

背包问题概述

        背包问题 (Knapsack problem) 是⼀种组合优化的 NP完全问题。

        问题可以描述为：给定⼀组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

根据物品的个数，分为如下几类：

• 01 背包问题：每个物品只有⼀个。
• 完全背包问题：每个物品有无限多个。
• 多重背包问题：每件物品最多有 si 个。
• 混合背包问题：每个物品会有上⾯三种情况……。
• 分组背包问题：物品有 n 组，每组物品⾥有若干个，每组里最多选⼀个物品。

其中上述分类里面，根据背包是否装满，又分为两类：

• 不一定装满背包
• 背包一定装满

优化方案：

• 空间优化 – 滚动数组
• 单调队列优化
• 贪心优化

根据限定条件的个数，⼜分为两类：

• 限定条件只有⼀个：比如体积 -> 普通的背包问题
• 限定条件有两个：比如体积 + 重量 -> ⼆维费用背包问题

根据不同的问法，又分为很多类：

• 输出方案
• 求方案总数
• 最优方案
• 方案可行性

        因此，背包问题种类非常繁多，题型非常丰富，难度也是非常难以捉摸。但是，尽管种类非常多，都是从 01 背包问题演化过来。所以：⼀定要把 01 背包问题学好。

01 背包问题

01背包⭐⭐ 

【模板】01背包_牛客题霸_牛客网 (nowcoder.com)

【算法原理】

第一问

#：状态表示：

        根据「经验 + 题目要求」我们继续尝试「用 i 位置为结尾」结合「题目要求」得到，dp[ i ]表示：从前 i 个物品中挑选，总体积不超过 j ，所有选法中，能挑选出来的最大价值。（也看出来划了杠，看似很完美，但其实是错的），因为一个背包是有体积的，有体积为关键的背包仅仅看第几个物品是没用的。

        我们需要将背包的体积也需要包含进去，d[ i ][ j ]表示：从前 i 个物品中挑选，总体积不超过 j ，所有选法中，能挑选出来的最大价值。

#：状态转移方程：

线性 dp 状态转移方程分析方式，⼀般都是根据「最后⼀步」的状况，来分情况讨论：

• 不选第 i 个物品：相当于就是去前 i – 1 个物品中挑选，并且总体积不超过 j，此时 dp[ i ][ j ] = dp[ i – 1 ][ j ]。
• 选择第 i 个物品：那么我就只能去前 i – 1 个物品中，挑选总体积不超过 j – v[ i ] 的物品。此时 dp[ i ][ j ] = dp[ i – 1 ][ j – v[ i ] ] + w[ i ]。但是这种状态不⼀定存在，因此需要特判⼀下。

        综上，状态转移方程为：dp[ i ][ j ] = max(dp[ i – 1 ][ j ], dp[ i – 1 ][ j – v[ i ] ] + w[ i ])。

#：初始化：

       我们多加⼀行，方便我们的初始化，此时仅需将第⼀行初始化为 0 即可。因为什么也不选，也能满足体积不小于 j 的情况，此时的价值为 0 。

#：填表顺序：

        根据「状态转移方程」，我们仅需「从上往下」填表即可。

#：返回值：

        根据「状态表示」，返回 dp[n][V] 。 

第二问

#：状态表示：

        根据「经验 + 题目要求」我们继续尝试「用 i 位置为结尾」结合「题目要求」得到，dp[ i ][ j ] 表示：从前 i 个物品中挑选，总体积「正好」等于 j ，所有的选法中，能挑选出来的最⼤价值。

#：状态转移方程：

• dp[ i ][ j ] = max(dp[ i – 1 ][ j ], dp[ i – 1 ][ j – v[ i ] ] + w[ i ]) 。

        但是在使用 dp[ i – 1 ][ j – v[ i ] ] 的时候，不仅要判断 j >= v[ i ] ，⼜要判断 dp[ i – 1 ][ j – v[ i ] ] 表示的情况是否存在，也就是 dp[ i – 1 ][ j – v[ i ] ] != -1 。

#：初始化：

我们多加一行，方便我们的初始化：

• 第一个格子为 0 ，因为正好能凑齐体积为 0 的背包。
• 但是第一行后面的格子都是 -1 ，因为没有物品，无法满足体积大于 0 的情况。

#：填表顺序：

        根据「状态转移方程」，我们仅需「从上往下」填表即可。

#：返回值：

        由于最后可能凑不成体积为 V 的情况，因此返回之前需要「特判」⼀下。

C++ 算法代码

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <memory.h>
using namespace std;

int main()
{
    int n = 0, V = 0;
    cin >> n >> V;
    vector<pair<int, int>> val;
    val.reserve(n + 1);
    val.push_back(make_pair(0, 0));
    for (int i = n; i > 0 ; i--) {
        int v = 0, w = 0;
        cin >> v >> w;
        val.push_back(make_pair(v, w));
    }

    // 背包不满的时候的最大价值
    // 1、创建dp表
    vector<vector<int>> dp(n + 1, vector<int>(V + 1, 0));

    // 2、初始化 

    // 3、填表
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < V + 1; j++)
        {
            dp[i][j] = dp[i - 1][j];

            if (j >= val[i].first)
                dp[i][j] = max(dp[i][j],
                               dp[i - 1][j - val[i].first] + val[i].second);
        }
    }

    // 4、返回值
    cout << dp[n][V] << endl;


    // 背包满的时候的最大价值
    // 1、创建dp表
    fill(dp.begin(), dp.end(), vector<int>(V + 1, 0));

    // 2、初始化
    for (int i = 1; i < V + 1; i++)
        dp[0][i] = -1;

    // 3、填表
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < V + 1; j++)
        {
            dp[i][j] = dp[i - 1][j];

            if (j >= val[i].first && dp[i - 1][j - val[i].first] != -1)
                dp[i][j] = max(dp[i][j],
                               dp[i - 1][j - val[i].first] + val[i].second);
        }
    }

    // 4、返回值
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;

    return 0;
}

复杂度分析

• 时间复杂度：O(n*m)，两层for循环。
• 空间复杂度：O(n*m)。

【空间优化 – 滚动数组】

        首先根据状态方程：dp[ i ][ j ] = max(dp[ i – 1 ][ j ], dp[ i – 1 ][ j – v[ i ] ] + w[ i ])，可以发现只是和两行有关，所以我们就可以首先用两个一维数组解决。

        由前一行的两个元素推出需求的位置。根据此我们可以推出一个一维数组解决，只不过有一个问题

        所以，防止在未使用的时候出现被更改的情况，建议以从右往左的顺序进行。

C++ 算法代码

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <memory.h>
using namespace std;

int main()
{
    int n = 0, V = 0;
    cin >> n >> V;
    vector<pair<int, int>> val;
    val.reserve(n + 1);
    val.push_back(make_pair(0, 0));
    for (int i = n; i > 0 ; i--) {
        int v = 0, w = 0;
        cin >> v >> w;
        val.push_back(make_pair(v, w));
    }

    // 背包不满的时候的最大价值
    // 1、创建dp表
    vector<int> dp(V + 1, 0);

    // 2、初始化 

    // 3、填表
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = V; j >= val[i].first; j--)
        {
            if (j >= val[i].first)
                dp[j] = max(dp[j], dp[j - val[i].first] + val[i].second);
        }
    }

    // 4、返回值
    cout << dp[V] << endl;


    // 背包满的时候的最大价值
    // 1、创建dp表
    fill(dp.begin(), dp.end(), -1);

    // 2、初始化
    dp[0] = 0;

    // 3、填表
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = V; j >= val[i].first; j--)
        {
            if (dp[j - val[i].first] != -1)
                dp[j] = max(dp[j], dp[j - val[i].first] + val[i].second);
        }
    }

    // 4、返回值
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
    return 0;
}

优化细节：

        因为如果出现 j >= val[i].first；那么 max(dp[j], dp[j – val[i].first] + val[i].second)；没有执行的意义会越界。

        未优化的时候因为需要 dp[ i ][ j ] = dp[i – 1][ j ]；所以必须将第二层循环迭代完成，但是此处由于已经优化为一维数组，所以无需继续迭代。

复杂度分析

• 时间复杂度：O(n*m)，两个两层for循环。
• 空间复杂度：O(n)。

分割等和子集⭐⭐

416. 分割等和子集 – 力扣（LeetCode）

【算法原理】 

对于类01背包问题

• 转换：对应的题目提供的要素，时常是需要一个转换过程的（十分重要）。

        重点在于每一个元素的选和不选的问题，也就是01背包关键的地方。

• 01背包 “模板”：不是说里面的东西都是照抄过来的，而是里面的分析思路 “模板”，根据题目进行一定方式的微调。

        将其转化为「熟悉」的题型，如果数组能够被分成两个相同元素之和相同的子集，那么原数组必须有下面几个性质：

• 所有元素之和应该是⼀个偶数。
• 挑选⼀些数，这些数的总和应该等于数组总和的⼀半。

        根据前两个性质，我们可以提前判断数组能够被划分，根据最后⼀个性质，我们发现问题就转化成了「01 背包」的模型：

• 数组中的元素只能选择⼀次。
• 每个元素面临被选择或者不被选择的处境。
• 选出来的元素总和要等于所有元素总和的⼀半。

        其中，数组内的元素就是物品，总和就是背包。 那么我们就可以⽤背包模型的分析方式，来处理这道题。 「不要背」01背包的状态转移方程，我们要记住的是分析问题的模式，用这种分析问题的模式来解决问题。

 #：状态表示：

        根据「经验 + 题目要求」我们继续尝试「用 i 位置为结尾」结合「题目要求」得到，dp[ i ][ j ] 表示在前 i 个元素中选择，所有的选法中，能否凑成总和为 j 这个数。

#：状态转移方程：

根据「最后⼀个位置」的元素，结合题目的要求，分情况讨论：

• 不选择 nums[ i ] ：那么我们是否能够凑成总和为 j ，就要看在前 i – 1 个元素中选，能否凑成总和为 j 。根据状态表示：dp[ i ][ j ] = dp[ i – 1 ][ j ]。
• 选择 nums[ i ] ：这种情况下是有前提条件的，此时的 nums[ i ] 应该是小于等于 j 。因为如果这个元素都比要凑成的总和大，选择它就没有意义呀。那么我们是否能够凑成总和为 j ，就要看在前 i – 1 个元素中选，能否凑成总和为 j – nums[ i ] 。根据状态表示：dp[ i ][ j ] = dp[ i – 1 ][ j – nums[ i ]]。

        综上所述，两种情况下只要有⼀种能够凑成总和为 j ，那么这个状态就是 true 。因此，状态转移方程为：dp[ i ][ j ] = dp[ i – 1 ][ j ]；if(nums[ i ] <= j)  dp[ i ][ j ] = dp[ i ][ j ] || dp[ i – 1 ][ j – nums[ i ]]。

#：初始化：

        由于添加了一行一列，因此我们可以先把第一行初始化，第一行表示不选择任何元素，要凑成目标和 j 。只有当目标和为 0 的时候才能做到，因此第一行仅需初始化第⼀个元素 dp[0][0] = true。一列中不放任何元素就可以了，于是第一列全为true。

#：填表顺序：

        根据「状态转移方程」，我们需要「从上往下」填写每一行，每一行的顺序是「无所谓的」。

#：返回值：

        根据「状态表示」，返回 dp[ n ][ aim ] 的值。其中 n 表示数组的大小， aim 表示要凑的目标和。

C++ 算法代码 

class Solution {
public:
    bool canPartition(vector<int>& nums) {

        int n = nums.size();
        int sum = 0;
        for(auto val : nums)
            sum += val;

        if(sum % 2) return false;

        // 1、创建dp表
        vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1, false));

        // 2、初始化
        for(int i = 0; i < n; i++)
            dp[i][0] = true;

        // 3、填表
        for(int i = 1; i < n + 1; i++)
        {
            for(int j = 1; j < sum + 1; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= nums[i - 1])
                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
            }
        }

        // 4、返回值
        return dp[n][sum / 2];
    }
};

【空间优化 – 滚动数组】 

        原理与第一道经典的01背包问题一样。

C++ 算法代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {

        int n = nums.size();
        int sum = 0;
        for(auto val : nums)
            sum += val;

        if(sum % 2) return false;

        // 1、创建dp表
        vector<bool> dp(sum + 1, false);

        // 2、初始化
        dp[0] = true;

        // 3、填表
        for(int i = 1; i < n + 1; i++)
        {
            for(int j = sum + 1; j >= nums[i - 1]; j--)
                dp[j] = dp[j] || dp[j - nums[i - 1]];
        }

        // 4、返回值
        return dp[sum / 2];
    }
};

目标和⭐⭐

494. 目标和 – 力扣（LeetCode）

        用数学知识分析转化成我们常见的「背包模型」的问题。 设我们最终选取的结果中，前面加 + 号的数字之和为 a ，前面加 – 号的数字之和为 b ，整个数组的总和为 sum ，于是我们有：

• a + b = sum
• a – b = target

        上面两个式子消去 b 之后，可以得到 a = (sum + target) / 2 也就是说，我们仅需在 nums 数组中选择⼀些数，将它们凑成和为 (sum + target) / 2 即可。

【算法原理】 

 #：状态表示：

        根据「经验 + 题目要求」我们继续尝试「用 i 位置为结尾」结合「题目要求」得到，dp[ i ][ j ] 表示：在前 i 个数中选，总和正好等于 j ，⼀共有多少种选法。

#：状态转移方程：

根据「最后⼀个位置」的元素，结合题目的要求，我们有「选择」最后⼀个元素或者「不选择」最后⼀个元素两种策略：

• 不选 nums[ i ] ：那么我们凑成总和 j 的总方案，就要看在前 i – 1 个元素中选，凑成总和为 j 的方案数。根据状态表示：dp[ i ][ j ] = dp[ i – 1 ][ j ]。
• 选择 nums[ i ] ：这种情况下是有前提条件的，此时的 nums[ i ] 应该是小于等于 j 。因为如果这个元素都比要凑成的总和大，选择它就没有意义呀。那么我们能够凑成总和为 j 的方案数，就要看在前 i – 1 个元素中选，能否凑成总和为 j – nums[ i ] 。根据状态表示：dp[ i ][ j ] += dp[ i  – 1 ][ j – nums[ i ]]。

         综上所述，两种情况如果存在的话，应该要累加在⼀起。因此，状态转移方程为：dp[ i ][ j ] = dp[ i – 1 ][ j ]； if(nums[ i ] <= j)  dp[ i ][ j ] += dp[ i – 1 ][ j – nums[ i ]]。

#：初始化：

        由于需要用到「上一行」的数据，因此我们可以先把第一行初始化。第一行表示不选择任何元素，要凑成目标和 j 。只有当目标和为 0 的时候才能做到，因此第⼀行仅需初始化第⼀个元素 dp[0][0] = 1。

#：填表顺序：

        根据「状态转移方程」，我们需要「从上往下」填写每一行，每一行的顺序是「无所谓的」。

#：返回值：

        根据「状态表示」，返回 dp[ n ][ aim ] 的值。其中 n 表示数组的大小， aim 表示要凑的目标和。

C++ 算法代码 

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(auto val : nums)
            sum += val;

        int aim = (sum + target) / 2;
        if(aim < 0 || (sum + target) % 2) return 0;

        int n = nums.size();

        // 1、创建dp表
        vector<vector<int>> dp(n + 1, vector<int>(aim + 1, 0));

        // 2、初始化
        dp[0][0] = 1;
        
        // 3、填表
        for(int i = 1; i < n + 1; i++)
        {
            for(int j = 0; j < aim + 1; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= nums[i - 1])
                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
            }
        }

        // 4、返回值
        return dp[n][aim];
    }
};

【空间优化 – 滚动数组】 

        原理与第一道经典的01背包问题一样。

C++ 算法代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(auto val : nums)
            sum += val;

        int aim = (sum + target) / 2;
        if(aim < 0 || (sum + target) % 2) return 0;

        int n = nums.size();

        // 1、创建dp表
        vector<int> dp(aim + 1, 0);

        // 2、初始化
        dp[0] = 1;
        
        // 3、填表
        for(int i = 1; i < n + 1; i++)
        {
            for(int j = aim; j >= nums[i - 1]; j--)
                dp[j] += dp[j - nums[i - 1]];
        }

        // 4、返回值
        return dp[aim];
    }
};

最后一块石头的重量Ⅱ⭐⭐⭐ 

1049. 最后一块石头的重量 II – 力扣（LeetCode）

【算法原理】 

先将问题「转化」成我们熟悉的题型。

• 任意两块石头在⼀起粉碎，重量相同的部分会被丢掉，重量有差异的部分会被留下来。那就相当于在原始的数据的前面，加上「加号」或者「减号」，是最终的结果最小即可。也就是说把原始的石头分成两部分，两部分的和越接近越好。

• 又因为当所有元素的和固定时，分成的两部分越接近数组「总和的⼀半」，两者的差越小。

        因此问题就变成了：在数组中选择⼀些数，让这些数的和尽量接近 sum / 2 ，如果把数看成物品，每个数的值看成体积和价值，问题就变成了「01 背包问题」。

 #：状态表示：

        根据「经验 + 题目要求」我们继续尝试「用 i 位置为结尾」结合「题目要求」得到，dp[ i ][ j ] 表示在前 i 个元素中选择，总和不超过 j，此时所有元素的「最大和」。

#：状态转移方程：

根据「最后⼀个位置」的元素，结合题目的要求，分情况讨论：

• 不选 stones[i] ：那么我们是否能够凑成总和为 j ，就要看在前 i – 1 个元素中选，能否凑成总和为 j 。根据状态表示：dp[ i ][ j ] = dp[ i – 1 ][ j ] 。
• 选择 stones[i] ：这种情况下是有前提条件的，此时的 stones[ i ] 应该是⼩于等于 j 。因为如果这个元素都⽐要凑成的总和⼤，选择它就没有意义呀。那么我们是否能够凑成总和为 j ，就要看在前 i – 1 个元素中选，能否凑成总和为 j – stones[ i ] 。根据状态表示：dp[ i ][ j ] = max(dp[ i ][ j ], dp[ i – 1 ][ j – stones[ i ]] + stones[ i ]); 。

         综上所述，我们要的是最大价值。因此，状态转移方程为：dp[ i ][ j ] = dp[ i – 1 ][ j ]； if(j >= stones[ i ])  dp[ i ][ j ] = max(dp[ i ][ j ], dp[ i – 1 ][ j – stones[ i ]] + stones[ i ]); 。

#：初始化：

        由于需要用到上一行的数据，因此我们可以先把第一行初始化。第一行表示「没有石子」。因此想凑成目标和 j ，最大和都是 0 。

#：填表顺序：

        根据「状态转移方程」，我们需要「从上往下」填写每一行，每一行的顺序是「无所谓的」。

#：返回值：

• 根据「状态表示」，先找到最接近 sum / 2 的最大和 dp[n][sum / 2] 。
• 因为我们要的是两堆石子的差，因此返回 sum – 2 * dp[n][sum / 2] 。

C++ 算法代码 

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {

        int n = stones.size();
        int sum = 0;
        for(auto val : stones)
            sum += val;
        int half = sum / 2;

        // 1、创建dp表
        vector<vector<int>> dp(n + 1, vector<int>(half + 1, 0));

        // 2、初始化 -- 已经在创建dp表中初始化

        // 3、填表
        for(int i = 1; i < n + 1; i++)
        {
            for(int j = 1; j < half + 1; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= stones[i - 1])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
            }
        }
        return sum - 2 * dp[n][half];
    }
};

【空间优化 – 滚动数组】 

        原理与第一道经典的01背包问题一样。

C++ 算法代码

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {

        int n = stones.size();
        int sum = 0;
        for(auto val : stones)
            sum += val;
        int half = sum / 2;

        // 1、创建dp表
        vector<int> dp(half + 1, 0);

        // 2、初始化 -- 已经在创建dp表中初始化

        // 3、填表
        for(int i = 1; i < n + 1; i++)
        {
            for(int j = half; j >= stones[i - 1]; j--)
                dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
        }
        return sum - 2 * dp[half];
    }
};