qidao123.com技术社区-IT企服评测·应用市场

标题: 算法沉淀——动态规划之完全背包问题（leetcode真题剖析） [打印本页]
作者: 莫张周刘王    时间: 2025-5-3 18:31
标题: 算法沉淀——动态规划之完全背包问题（leetcode真题剖析）


  
完全背包问题是背包问题的一种变体，与01背包问题差别，它允许你对每种物品进行多次选择。详细来说，给定一个固定容量的背包，一组物品，每个物品有重量和价值，目的是找到在背包容量范围内，使得背包中的物品总价值最大的组合。
相较于01背包问题，完全背包问题允许对每个物品进行多次选择，即每个物品都有无穷件可用。
动态规划解法：
例子：
假设有如下物品：
  1. 物品1：重量=2，价值=3
  2. 物品2：重量=3，价值=4
  3. 物品3：重量=4，价值=5
复制代码
背包容量为W=8，我们要求解在这个条件下的最大总价值。
按照上述动态规划解法，构建状态转移表如下：
  1. 重量/价值      0   1   2   3   4   5   6   7   8
  2.   ----------------------------------------------
  3.   物品0        0   0   0   0   0   0   0   0   0
  4.   物品1        0   0   3   6   9   12  15  18  21
  5.   物品2        0   0   3   6   9   12  15  18  21
  6.   物品3        0   0   3   6   9   12  15  18  21
复制代码
因此，最终结果为dp[3][8] = 21，表示在背包容量为8的环境下，最大总价值为21。这意味着最优解是选择物品1，物品2和物品3各两件放入背包。
01.【模板】完全背包

题目链接：https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc?tpId=230&tqId=2032575&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
形貌
你有一个背包，最多能容纳的体积是V。
现在有n种物品，每种物品有任意多个，第i种物品的体积为vi,价值为wi。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰恰装满，求至多能装多大价值的物品？
输入形貌：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个vi和wi表示第i种物品的体积和价值。
1≤n,V≤1000
输出形貌：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
示例1
输入：
  1. 2 6
  2. 5 10
  3. 3 1
复制代码
输出：
  1. 10
  2. 2
复制代码
示例2
输入：
  1. 3 8
  2. 3 10
  3. 9 1
  4. 10 1
复制代码
输出：
  1. 20
  2. 0
复制代码
说明：
  1. 无法恰好装满背包。
复制代码
示例3
输入：
  1. 6 13
  2. 13 189
  3. 17 360
  4. 19 870
  5. 14 184
  6. 6 298
  7. 16 242
复制代码
输出：
  1. 596
  2. 189
复制代码
说明：
  1. 可以装5号物品2个，达到最大价值298*2=596，若要求恰好装满，只能装1个1号物品，价值为189.
复制代码
思路
第一问：

  • 状态表示：

    • dp[j] 表示从前 i 个物品中挑选，总体积不凌驾 j，所有选法中能挑选出的最大价值。

  • 状态转移方程：

    • 根据最后一步的状况，分环境讨论：

      • 选 0 个第 i 个物品：相称于去前 i - 1 个物品中挑选，总体积不凌驾 j，最大价值为 dp[i - 1][j]。
      • 选 1 个第 i 个物品：相称于去前 i - 1 个物品中挑选，总体积不凌驾 j - v。此时最大价值为 dp[i - 1][j - v] + w。

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

  • 初始化：

    • 多加一行，将第一行初始化为 0，由于什么也不选时，满足体积不小于 j 的环境，此时价值为 0。

  • 填表顺序：

    • 从上往下填表。

  • 返回值：

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

第二问：

  • 状态表示：

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

  • 状态转移方程：

    • dp[j] = max(dp[i - 1][j], dp[j - v] + w)。
    • 在使用 dp[j - v] 时，须要判断 j >= v 且 dp[j - v] 表示的状态是否存在，即 dp[j - v] != -1。

  • 初始化：

    • 多加一行，将第一个格子设置为 0，由于正好能凑齐体积为 0 的背包；但是第一行后面的格子都设置为 -1，由于没有物品，无法满足体积大于 0 的环境。

  • 填表顺序：

    • 从上往下填表。

  • 返回值：

    • 由于最后大概凑不成体积为 V 的环境，因此返回之前须要特判一下。

空间优化：
对于背包问题，一般都可以使用「滚动数组」来进行空间上的优化，即淘汰状态表示的维度。
在 01 背包问题中，优化的结果为：

  • 删掉所有的横坐标。
  • 修改一下 j 的遍历顺序。
这样的优化是由于在盘算 dp[j] 时，只依赖于上一行 dp[i-1][j] 和 dp[i-1][j-v]，而 dp[i-1][j-v] 在当前行的盘算过程中已经被更新过，因此不须要保留整个二维数组。
代码
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. using namespace std;
  6. const int N=1002;
  7. int n,V,v[N],w[N];
  8. int dp[N][N];
  10. int main() {
  11.     cin>>n>>V;
  12.     for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
  14.     for(int i=1;i<=n;i++)
  15.         for(int j=0;j<=V;j++)
  16.         {
  17.             dp[i][j]=dp[i-1][j];
  18.             if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
  19.         }
  20.     cout<<dp[n][V]<<endl;
  22.     memset(dp,0,sizeof dp);
  23.     for(int j=1;j<=V;j++) dp[0][j]=-1;
  24.     for(int i=1;i<=n;i++)
  25.         for(int j=0;j<=V;j++)
  26.         {
  27.             dp[i][j]=dp[i-1][j];
  28.             if(j>=v[i]&&dp[i][j-v[i]]!=-1)
  29.                 dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
  30.         }
  31.     cout<<(dp[n][V]==-1?0:dp[n][V])<<endl;
  33.     return 0;
  34. }
复制代码
02.零钱兑换

题目链接：https://leetcode.cn/problems/coin-change/
给你一个整数数组 coins ，表示差别面额的硬币；以及一个整数 amount ，表示总金额。
盘算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能构成总金额，返回 -1 。
你可以以为每种硬币的数量是无穷的。
示例 1：
  1. 输入：coins = [1, 2, 5], amount = 11
  2. 输出：3
  3. 解释：11 = 5 + 5 + 1
复制代码
示例 2：
  1. 输入：coins = [2], amount = 3
  2. 输出：-1
复制代码
示例 3：
  1. 输入：coins = [1], amount = 0
  2. 输出：0
复制代码
提示：


  • 1 <= coins.length <= 12
  • 1 <= coins <= 231 - 1
  • 0 <= amount <= 104
思路

  • 状态表示：

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

  • 状态转移方程：

    • 在完全背包问题中，每个硬币可以选无穷个，因此须要分多种环境讨论：

      • 选 0 个第 i 个硬币：相称于去前 i - 1 个硬币中挑选，总和正好等于 j。此时最少的硬币个数为 dp[i - 1][j]。
      • 选 1 个第 i 个硬币：相称于去前 i - 1 个硬币中挑选，总和正好等于 j - coins。由于挑选了一个第 i 个硬币，此时最少的硬币个数为 dp[j - coins] + 1。

    • 综上，状态转移方程为：dp[j] = min(dp[i - 1][j], dp[j - coins] + 1)。

  • 初始化：

    • 初始化第一行，将第一个位置设置为 0，由于正好能凑齐总和为 0 的硬币；其余位置设置为无穷大。

  • 填表顺序：

    • 从上往下填表。

  • 返回值：

    • 根据状态表示，返回 dp[n][V]。但要特判一下，由于有大概凑不到。

代码
  1. class Solution {
  2.     const int INF=0x3f3f3f3f;
  3. public:
  4.     int coinChange(vector<int>& coins, int amount) {
  5.         int n=coins.size();
  6.         vector<vector<int>> dp(n+1,vector<int>(amount+1));
  8.         for(int j=1;j<=amount;j++) dp[0][j]=INF;
  9.         for(int i=1;i<=n;i++)
  10.             for(int j=0;j<=amount;j++)
  11.             {
  12.                 dp[i][j]=dp[i-1][j];
  13.                 if(j>=coins[i-1]) dp[i][j]=min(dp[i][j],dp[i][j-coins[i-1]]+1);
  14.             }
  15.         return dp[n][amount]>=INF?-1:dp[n][amount];
  16.     }
  17. };
复制代码
03.零钱兑换 II

题目链接：https://leetcode.cn/problems/coin-change-ii/
给你一个整数数组 coins 表示差别面额的硬币，另给一个整数 amount 表示总金额。
请你盘算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无穷个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
  1. 输入：amount = 5, coins = [1, 2, 5]
  2. 输出：4
  3. 解释：有四种方式可以凑成总金额：
  4. 5=5
  5. 5=2+2+1
  6. 5=2+1+1+1
  7. 5=1+1+1+1+1
复制代码
示例 2：
  1. 输入：amount = 3, coins = [2]
  2. 输出：0
  3. 解释：只用面额 2 的硬币不能凑成总金额 3 。
复制代码
示例 3：
  1. 输入：amount = 10, coins = [10]
  2. 输出：1
复制代码
提示：


  • 1 <= coins.length <= 300
  • 1 <= coins <= 5000
  • coins 中的所有值 互不雷同
  • 0 <= amount <= 5000
思路

  • 状态表示：

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

  • 状态转移方程：

    • 在完全背包问题中，每个硬币可以选无穷个，因此须要分多种环境讨论：

      • 选 0 个第 i 个硬币：相称于去前 i - 1 个硬币中挑选，总和正好等于 j。此时的选法数为 dp[i - 1][j]。
      • 选 1 个第 i 个硬币：相称于去前 i - 1 个硬币中挑选，总和正好等于 j - coins。由于挑选了一个第 i 个硬币，此时的选法数为 dp[j - coins] + 1。

    • 综上，状态转移方程为：dp[j] = dp[i - 1][j] + dp[j - coins] + 1。

  • 初始化：

    • 初始化第一行，表示没有物品，总和正好为 0 的环境。只有一种环境，即 dp[0][0] = 1；其余位置都为 0 种环境。

  • 填表顺序：

    • 从上往下填表。

  • 返回值：

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

代码
  1. class Solution {
  2. public:
  3.     int change(int amount, vector<int>& coins) {
  4.         int n=coins.size();
  5.         vector<vector<int>> dp(n+1,vector<int>(amount+1));
  6.         dp[0][0]=1;
  7.         for(int i=1;i<=n;i++)
  8.             for(int j=0;j<=amount;j++){
  9.                 dp[i][j]=dp[i-1][j];
  10.                 if(j>=coins[i-1]) dp[i][j]=dp[i][j]+dp[i][j-coins[i-1]];
  11.             }
  12.         return dp[n][amount];
  13.     }
  14. };
复制代码
04.完全平方数

题目链接：https://leetcode.cn/problems/perfect-squares/
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
  1. 输入：n = 12
  2. 输出：3
  3. 解释：12 = 4 + 4 + 4
复制代码
示例 2：
  1. 输入：n = 13
  2. 输出：2
  3. 解释：13 = 4 + 9
复制代码
提示：


  • 1 <= n <= 104
思路

  • 状态表示：

    • 在这个问题中，状态表示我们须要找到使得和为 n 的最少完全平方数的数量。因此，我们可以定义状态 dp[j]，其中 i 表示使用前 i 个完全平方数，j 表示目的和为 j。dp[j] 的值表示使用前 i 个完全平方数达到和为 j 时的最小数量。

  • 状态转移方程：

    • 根据问题的特点，我们可以得到状态转移方程：
      dp[j]=min(dp[j],dp[j-i*i]+1);
      其中，i*i表示第 i 个完全平方数。

  • 初始化：

    • 在初始化阶段，我们须要初始化第一行和第一列的值。对于第一行，由于使用零个完全平方数就能达到和为 0，所以 dp[0][0] = 0。对于其余的 dp[0][j]，由于没有完全平方数可用，我们设为一个较大的值（代表不大概达到这个和）。对于第一列，由于使用任何完全平方数都可以达到和为 0，所以 dp[0] = 0。

  • 填表顺序：

    • 遍历顺序通常是根据状态转移方程中的依赖关系来确定的。在这里，我们可以先遍历使用的完全平方数 i，然后遍历目的和 j。

  • 返回值：

    • 返回结果是在最后一行 dp[m][n] 中，其中 m 表示完全平方数的个数，n 表示目的和。

代码
  1. class Solution {
  2.     const int INF=0x3f3f3f3f;
  3. public:
  4.     int numSquares(int n) {
  5.         int m=(int)sqrt(n);
  6.         vector<vector<int>> dp(m+1,vector<int>(n+1));
  7.         for(int j=1;j<=n;j++) dp[0][j]=INF;
  9.         for(int i=1;i<=m;i++)
  10.             for(int j=0;j<=n;j++){
  11.                 dp[i][j]=dp[i-1][j];
  12.                 if(j>=i*i) dp[i][j]=min(dp[i][j],dp[i][j-i*i]+1);
  13.             }
  14.         return dp[m][n];
  15.     }
  16. };
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/) Powered by Discuz! X3.4