专题九：完全背包

最新推荐文章于 2025-04-01 20:15:49 发布

置顶 დ旧言~

最新推荐文章于 2025-04-01 20:15:49 发布

阅读量1k

点赞数 38

分类专栏：动态规划算法文章标签：推荐算法动态规划算法 leetcode

本文链接：https://blog.csdn.net/AAlykk/article/details/144753285

版权

动态规划算法专栏收录该内容

10 篇文章

订阅专栏

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

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

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

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

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

一、算法讲解

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

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

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

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

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

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

优化⽅案：

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

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

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

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

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

二、算法习题

2.1 第一题

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

题目描述：

算法思路：

我们先解决第⼀问：

1. 状态表⽰：

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

2. 状态转移⽅程：

线性 dp 状态转移⽅程分析⽅式，⼀般都是根据最后⼀步的状况，来分情况讨论。但是最后⼀个物品能选很多个，因此我们的需要分很多情况：

选 0 个第 i 个物品：此时相当于就是去前 i - 1 个物品中挑选，总体积不超过 j 。此时最⼤价值为 dp[i - 1][j] ；
选 1 个第 i 个物品：此时相当于就是去前 i - 1 个物品中挑选，总体积不超过 j -v[i] 。因为挑选了⼀个 i 物品，此时最⼤价值为 dp[i - 1][j - v[i]] +w[i] ；
选 2 个第 i 个物品：此时相当于就是去前 i - 1 个物品中挑选，总体积不超过 j- 2 * v[i] 。因为挑选了两个 i 物品，此时最⼤价值为 dp[i - 1][j - 2 *v[i]] + 2 * w[i] ；

综上，我们的状态转移⽅程为：

dp[i][j]=max(dp[i-1][j], dp[i-1][j-v[i]]+w[i], dp[i-1][j-2*v[i]]+2*w[i]...)

当我们发现，计算⼀个状态的时候，需要⼀个循环才能搞定的时候，我们要想到去优化。优化的⽅向就是⽤⼀个或者两个状态来表⽰这⼀堆的状态，通常就是⽤数学的⽅式做⼀下等价替换。我们发现第⼆维是有规律的变化的，因此我们去看看 dp[i][j - v[i]] 这个状态：

dp[i][j-v[i]]=max(dp[i-1][j-v[i]],dp[i-1][j-2*v[i]]+w[i],dp[i-1][j-3*v[i]]+2*w[i]...)

我们发现，把 dp[i][j - v[i]] 加上 w[i] 正好和 dp[i][j] 中除了第⼀项以外的全部⼀致，因此我们可以修改我们的状态转移⽅程为：

dp[i][j] = max(dp[i - 1][j], dp[i][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][j - v[i]] + w[i]) 。但是在使⽤ dp[i][j - v[i]] 的时候，不仅要判断 j >= v[i] ，⼜要判断 dp[i][j -v[i]] 表⽰的情况是否存在，也就是 dp[i][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][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][j - v[i]] != -1)
                dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
        }
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
    return 0;
}

2.2 第二题

题目链接：322. 零钱兑换 - 力扣（LeetCode）

题目描述：

算法思路：

1. 状态表⽰：

dp[i][j] 表⽰：从前 i 个硬币中挑选，总和正好等于 j ，所有的选法中，最少的硬币个数。

2. 状态转移⽅程：

线性 dp 状态转移⽅程分析⽅式，⼀般都是根据「最后⼀步」的状况，来分情况讨论。但是最后⼀个物品能选很多个，因此我们的需要分很多情况：

选 0 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j 。此时最少的硬币个数为 dp[i - 1][j] ；
选 1 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j -v[i] 。因为挑选了⼀个 i 硬币，此时最少的硬币个数为 dp[i - 1][j -coins[i]] + 1 ；
选 2 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j- 2 * coins 。因为挑选了两个 i 硬币，此时最少的硬币个数为 dp[i - 1][j -2 * coins[i]] + 2 ；

结合我们在完全背包⾥⾯的优化思路，我们最终得到的状态转移⽅程为：

dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1) 。

这⾥教给⼤家⼀个技巧，就是相当于把第⼆种情况 dp[i - 1][j - coins[i]] + 1 ⾥⾯的 i - 1 变成 i 可。

3. 初始化：

初始化第⼀⾏即可。这⾥因为取 min ，所以我们可以把⽆效的地⽅设置成⽆穷⼤ (0x3f3f3f3f)因为这⾥要求正好凑成总和为 j ，因此，需要把第⼀⾏除了第⼀个位置的元素，都设置成⽆穷⼤。

4. 填表顺序：

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

5. 返回值：

根据「状态表⽰」，返回 dp[n][V] 。但是要特判⼀下，因为有可能凑不到。

代码呈现：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) 
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        const int INF = 0x3f3f3f3f;
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
        for (int j = 1; j <= amount; j++)
            dp[0][j] = INF;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= amount; j++) 
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i - 1])
                    dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
            }
        return dp[n][amount] >= INF ? -1 : dp[n][amount];
    }
};

2.3 第三题

题目链接：518. 零钱兑换 II - 力扣（LeetCode）

题目描述：

算法思路：

1. 状态表⽰：

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

2. 状态转移⽅程：

线性 dp 状态转移⽅程分析⽅式，⼀般都是「根据最后⼀步」的状况，来分情况讨论。但是最后⼀个物品能选很多个，因此我们的需要分很多情况：

选 0 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j 。此时最少的硬币个数为 dp[i - 1][j] ；
选 1 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j -v[i] 。因为挑选了⼀个 i 硬币，此时最少的硬币个数为 dp[i - 1][j -coins[i]] + 1 ；
选 2 个第 i 个硬币：此时相当于就是去前 i - 1 个硬币中挑选，总和正好等于 j- 2 * coins 。因为挑选了两个 i 硬币，此时最少的硬币个数为 dp[i - 1][j -2 * coins[i]] + 2 ；

结合我们在完全背包⾥⾯的「优化思路」，我们最终得到的状态转移⽅程为：

dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]] + 1 。

这⾥教给⼤家⼀个技巧，就是相当于把第⼆种情况 dp[i - 1][j - coins[i]] + 1 ⾥⾯的 i - 1 变成 i 即可。

3. 初始化：

初始化第⼀⾏即可。第⼀⾏表⽰没有物品，没有物品正好能凑能和为 0 的情况。因此 dp[0][0] = 1 ，其余位置都是 0 种情况。

4. 填表顺序：

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

5. 返回值：

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

代码呈现：

class Solution {
public:
    int change(int amount, vector<int>& coins) 
    {
        int n = coins.size();
        vector memo(n, vector<int>(amount + 1, -1)); // -1 表示没有计算过
        auto dfs = [&](this auto&& dfs, int i, int c) -> int 
        {
            if (i < 0)
                return c == 0 ? 1 : 0;
            int& res = memo[i][c]; // 注意这里是引用
            if (res != -1)  // 之前算过了
                return res;
            if (c < coins[i]) 
                return res = dfs(i - 1, c);
            return res = dfs(i - 1, c) + dfs(i, c - coins[i]);
        };
        return dfs(n - 1, amount);
    }
};

2.4 第四题

题目链接：279. 完全平方数 - 力扣（LeetCode）

题目描述：

算法思路：

1. 状态表⽰：

dp[i] 表⽰：和为 i 的完全平⽅数的最少数量。

2. 状态转移⽅程：

对于 dp[i] ，根据思路那⾥的分析我们知道，可以根据⼩于等于 i 的所有完全平⽅数 x 进⾏划分：

x = 1 时，最⼩数量为： 1 + dp[i - 1] ；
x = 4 时，最⼩数量为： 1 + dp[i - 4] ......⼀直枚举到 x <= i 为⽌。

为了⽅便枚举完全平⽅数，我们采⽤下⾯的策略： for(int j = 1; j * j <= i; j++)综上所述，状态转移⽅程为：

dp[i] = min(dp[i], dp[i - j * j] + 1)

3. 初始化：

当 n = 0 的时候，没法拆分，结果为 0 ；
当 n = 1 的时候，显然为 1 。

4. 填表顺序：

从左往右。

5. 返回值：

根据题意，返回 dp[n] 的值。

代码呈现：

class Solution {
public:
    int numSquares(int n) 
    {
        vector<int> dp(n + 1);
        dp[1] = 1;                   // 初始化
        for (int i = 2; i <= n; i++) // 枚举每个数
        {
            dp[i] = 1 + dp[i - 1];           // ⾄少等于 1 + dp[i - 1]
            for (int j = 2; j * j <= i; j++) // ⽤⼩于 i 的完全平⽅数划分区间
                dp[i] =
                    min(dp[i], dp[i - j * j] + 1); // 拿到所有划分区间内的最⼩值
        }
        // 返回结果
        return dp[n];
    }
};