【动态规划专栏】-- 01 背包问题 -- 动态规划经典题型_01背包问题动态规划算法

目录

背包问题概述

01 背包问题

01背包⭐⭐ 

【算法原理】

第一问

第二问

C++ 算法代码

复杂度分析

【空间优化 - 滚动数组】

C++ 算法代码

复杂度分析

分割等和子集⭐⭐

【算法原理】 

对于类01背包问题

C++ 算法代码 

【空间优化 - 滚动数组】 

C++ 算法代码

目标和⭐⭐

【算法原理】 

C++ 算法代码 

【空间优化 - 滚动数组】 

C++ 算法代码

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

【算法原理】 

C++ 算法代码 

【空间优化 - 滚动数组】 

C++ 算法代码

背包问题概述

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

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

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

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

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

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

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

01 背包问题

01背包⭐⭐ 

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

---

【算法原理】

第一问

#：状态表示：

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

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

#：状态转移方程：

• 不选第 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 ，所有的选法中，能挑选出来的最⼤价值。

#：状态转移方程：

#：初始化：

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

• 第一个格子为 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 这个数。

#：状态转移方程：

#：初始化：

#：填表顺序：

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

#：返回值：

        根据「状态表示」，返回 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 = target

【算法原理】 

 #：状态表示：

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

#：状态转移方程：

#：初始化：

#：填表顺序：

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

#：返回值：

        根据「状态表示」，返回 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）

---

【算法原理】 

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

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

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

 #：状态表示：

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

#：状态转移方程：

#：初始化：

#：填表顺序：

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

#：返回值：

• 根据「状态表示」，先找到最接近 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];
    }
};

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