当前位置：首页 > article >正文

专题八：背包问题

article 2024/12/24 7:07:53

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：了解什么是记忆化搜索，并且掌握记忆化搜索算法。

> 毒鸡汤：有些事情，总是不明白，所以我不会坚持。早安!

> 专栏选自：动态规划算法_დ旧言~的博客-CSDN博客

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

一、算法讲解

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

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

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

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

其中上述分类⾥⾯，根据背包是否装满，⼜分为两类：

不⼀定装满背包
背包⼀定装满

优化⽅案：

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

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

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

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

输出⽅案
求⽅案总数
最优⽅案
⽅案可⾏性

二、算法习题

2.1 第一题

题目链接：【模板】01背包_牛客题霸_牛客网

题目描述：

算法思路：

我们先解决第⼀问：

1. 状态表⽰：

dp[i][j] 表⽰：从前 i 个物品中挑选，总体积「不超过」 j ，所有的选法中，能挑选出来的最⼤价值。

2. 状态转移⽅程：

线性 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]) 。

3. 初始化：

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

4. 填表顺序：

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

5. 返回值：

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

接下来解决第⼆问：第⼆问仅需微调⼀下 dp 过程的五步即可。

因为有可能凑不⻬ j 体积的物品，因此我们把不合法的状态设置为 -1 。

1. 状态表⽰：

dp[i][j] 表⽰：从前 i 个物品中挑选，总体积「正好」等于 j ，所有的选法中，能挑选出来的最⼤价值。

2. 状态转移⽅程：

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 。

3. 初始化：

我们多加⼀⾏，⽅便我们的初始化：

第⼀个格⼦为 0 ，因为正好能凑⻬体积为 0 的背包；
但是第⼀⾏后⾯的格⼦都是 -1 ，因为没有物品，⽆法满⾜体积⼤于 0 的情况。

4. 填表顺序：

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

5. 返回值：

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

代码呈现：

#include <iostream>
#include <string.h>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N][N];
int main() 
{
// 读⼊数据
    cin >> n >> V;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
// 解决第⼀问
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= V; j++) { // 修改遍历顺序
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    cout << dp[n][V] << endl;
// 解决第⼆问
    memset(dp, 0, sizeof dp);
    for (int j = 1; j <= V; j++) dp[0][j] = -1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= V; j++) { // 修改遍历顺序
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i] && dp[i - 1][j - v[i]] != -1)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
    return 0;
}

2.2 第二题

题目链接：416. 分割等和子集 - 力扣（LeetCode）

题目描述：

算法思路：

如果数组能够被分成两个相同元素之和相同的⼦集，那么原数组必须有下⾯⼏个性质：

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

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

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

1. 状态表⽰：

dp[i][j] 表⽰在前 i 个元素中选择，所有的选法中，能否凑成总和为 j 这个数。

2. 状态转移⽅程：

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

不选择 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 - 1] <= j) dp[i][j] = dp[i][j] || dp[i - 1][j -nums[i]]

3. 初始化：

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

4. 填表顺序：

根据「状态转移⽅程」，我们需要「从上往下」填写每⼀⾏，每⼀⾏的顺序是「⽆所谓的」。

5. 返回值：

根据「状态表⽰」，返回 dp[n][aim] 的值。其中 n 表⽰数组的⼤⼩， aim 表⽰要凑的⽬标和。

6. 空间优化：

所有的「背包问题」，都可以进⾏空间上的优化。对于 01背包类型的，我们的优化策略是：

删掉第⼀维；
修改第⼆层循环的遍历顺序即可。

代码呈现：

class Solution {
public:
    bool canPartition(vector<int>& nums) 
    {
        int n = nums.size(), sum = 0;
        for (auto x : nums)
            sum += x;
        if (sum % 2)
            return false;  // 如果不能平分，直接返回 false
        int aim = sum / 2; // 定义⼀下⽬标值
        vector<vector<bool>> dp(n + 1, vector<bool>(aim + 1)); // 建表
        for (int i = 0; i <= n; i++)
            dp[i][0] = true;         // 初始化
        for (int i = 1; i <= n; i++) // 填表
            for (int j = 1; j <= aim; 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]];
            }
        // 返回结果
        return dp[n][aim];
    }
};

2.3 第三题

题目链接：494. 目标和 - 力扣（LeetCode）

题目描述：

算法思路：

本题可以直接⽤「暴搜」的⽅法解决。但是稍微⽤数学知识分析⼀下，就能转化成我们常⻅的「背
包模型」的问题。设我们最终选取的结果中，前⾯加 + 号的数字之和为 a ，前⾯加 - 号的数字之和为 b ，整个数组的总和为 sum ，于是我们有：

a + b = sum
a - b = target

上⾯两个式⼦消去 b 之后，可以得到 a = (sum + target) / 2也就是说，我们仅需在 nums 数组中选择⼀些数，将它们凑成和为 (sum + target) / 2 即可。问题就变成了 416. 分割等和⼦集这道题。我们可以⽤相同的分析模式，来处理这道题。

1. 状态表⽰：

dp[i][j] 表⽰：在前 i 个数中选，总和正好等于 j ，⼀共有多少种选法。

2. 状态转移⽅程：

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

不选 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 - 1] <= j) dp[i][j] = dp[i][j] += dp[i - 1][j - nums[i- 1]]

3. 初始化：

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

4. 填表顺序：

根据「状态转移⽅程」，我们需要「从上往下」填写每⼀⾏，每⼀⾏的顺序是「⽆所谓的」。

5. 返回值：

根据「状态表⽰」，返回 dp[n][aim] 的值。其中 n 表⽰数组的⼤⼩， aim 表⽰要凑的⽬标和。

6. 空间优化：

所有的「背包问题」，都可以进⾏空间上的优化。对于 01背包类型的，我们的优化策略是：

删掉第⼀维；
修改第⼆层循环的遍历顺序即可

代码呈现：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        int n = nums.size();
        int sum = 0;
        for (auto x : nums)
            sum += x;
        int aim = (sum + target) / 2;
        // 处理⼀下边界条件
        if (aim < 0 || (sum + target) % 2)
            return 0;
        vector<vector<int>> dp(n + 1, vector<int>(aim + 1)); // 建表
        dp[0][0] = 1;                                        // 初始化
        for (int i = 1; i <= n; i++)                         // 填表
            for (int j = 0; j <= aim; j++) 
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1])
                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
            }
        // 返回结果
        return dp[n][aim];
    }
};

2.4 第四题

题目链接：1049. 最后一块石头的重量 II - 力扣（LeetCode）

题目描述：

算法思路：

1. 状态表⽰：

dp[i][j] 表⽰在前 i 个元素中选择，总和不超过 j，此时所有元素的「最⼤和」。

2. 状态转移⽅程：

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

不选 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] = dp[i - 1][j - stones[i]] + stones[i] 。
综上所述，我们要的是最⼤价值。因此，状态转移⽅程为：dp[i][j] = dp[i - 1][j]if(j >= stones[i]) dp[i][j] = dp[i][j] + dp[i - 1][j - stones[i]]+ stones[i] 。

3. 初始化：

由于需要⽤到上⼀⾏的数据，因此我们可以先把第⼀⾏初始化。第⼀⾏表⽰「没有⽯⼦」。因此想凑成⽬标和 j ，最⼤和都是 0 。

4. 填表顺序：

根据「状态转移⽅程」，我们需要「从上往下」填写每⼀⾏，每⼀⾏的顺序是「⽆所谓的」。

5. 返回值：

根据「状态表⽰」，先找到最接近 sum / 2 的最⼤和 dp[n][sum / 2] ；
因为我们要的是两堆⽯⼦的差，因此返回 sum - 2 * dp[n][sum / 2] 。

6. 空间优化：

所有的背包问题，都可以进⾏「空间」上的优化。对于 01背包类型的，我们的优化策略是：

删掉第⼀维；
修改第⼆层循环的「遍历顺序」即可。

代码呈现：

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) 
    {
        // 1. 准备⼯作
        int sum = 0;
        for (auto x : stones)
            sum += x;
        int n = stones.size(), m = sum / 2;
        // 2. dp
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= m; 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]);
            }
        // 3. 返回结果
        return sum - 2 * dp[n][m];
    }
};