【C++基本算法】背包问题——完全背包

7. 背包问题——完全背包

【模板】完全背包

题目链接：

【模板】完全背包

要点：

• 完全背包核心逻辑：物品无限次选择，状态转移方程需从同一层转移（dp[i][j - v[i]]）
• 两类问题处理：
  • 第一问：最大价值（常规完全背包）
  • 第二问：恰好装满背包时的最大价值（需特殊初始化，不可达状态标记为 -1）
• 空间优化关键：
  • 完全背包遍历顺序为正序（与01背包逆序相反），确保同一物品可重复选

老师代码：

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

空间优化：

#include <iostream>
#include <string.h>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[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 = v[i]; j <= V; j++)dp[j] = max(dp[j], dp[j - v[i]] + w[i]);cout << dp[V] << endl;// 第⼆问memset(dp, 0, sizeof dp);for(int j = 1; j <= V; j++) dp[j] = -0x3f3f3f3f;//区别一for(int i = 1; i <= n; i++)for(int j = v[i]; j <= V; j++)dp[j] = max(dp[j], dp[j - v[i]] + w[i]);//区别二：没有if判断cout << (dp[V] < 0 ? 0 : dp[V]) << endl;return 0;
}

老师思路：

我们先解决第⼀问：

1. 状态表⽰：dp[i] [j] 表⽰：从前 i 个物品中挑选，总体积不超过 j ，所有的选法中，能挑选出来的最⼤价值。（这⾥是和 01背包⼀样哒）

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

   • i. 选 0 个第 i 个物品：此时相当于就是去前 i - 1 个物品中挑选，总体积不超过 j 。此时最⼤价值为 dp[i - 1] [j] ；
   • ii. 选 1 个第 i 个物品：此时相当于就是去前 i - 1 个物品中挑选，总体积不超过 j -v[i] 。因为挑选了⼀个 i 物品，此时最⼤价值为 dp[i - 1] [j - v[i]] + w[i]；
   • iii. 选 2 个第 i 个物品：此时相当于就是去前 i - 1 个物品中挑选，总体积不超过 j - 2 * v[i] 。因为挑选了两个 i 物品，此时最⼤价值为 dp[i - 1] [j - 2 * v[i]] + 2 * w[i] ；
   • iv. … 综上，我们的状态转移⽅程为：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. 初始化：我们多加⼀⾏，⽅便我们的初始化：i. 第⼀个格⼦为 0 ，因为正好能凑⻬体积为 0 的背包； ii. 但是第⼀⾏后⾯的格⼦都是 -1 ，因为没有物品，⽆法满⾜体积⼤于 0 的情况。

4. 填表顺序：根据状态转移⽅程，我们仅需从上往下填表即可。

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

空间优化：背包问题基本上都是利⽤滚动数组来做空间上的优化：

• i. 利⽤滚动数组优化；
• ii. 直接在原始代码上修改。在完全背包问题中，优化的结果为：i. 仅需删掉所有的横坐标。

我的代码：

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;int main()
{int n, V;cin >> n >> V;vector<int> v(n), w(n);//原始数据vector<vector<int>> dp(n + 1, vector<int>(V + 1));//dp表for(int i = 0; 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 - 1] >= 0) dp[i][j] = max(dp[i][j], dp[i][j - v[i - 1]] + w[i - 1]);}}cout << dp[n][V] << endl;//回答第二问//初始化vector<vector<int>> dp1(n + 1, vector<int>(V + 1));//我不知道为什么memset用不了for(int j = 1; j <= V; j++) dp1[0][j] = -1;//填表for(int i = 1; i <= n; i++){for(int j = 0; j <= V; j++){dp1[i][j] = dp1[i - 1][j];if(j - v[i - 1] >= 0 && dp1[i][j - v[i - 1]] != -1) dp1[i][j] = max(dp1[i][j], dp1[i][j - v[i - 1]] + w[i - 1]);}}cout << (dp1[n][V] == -1 ? 0 : dp1[n][V]) << endl;return 0;
}

空间优化：

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;int main()
{int n, V;cin >> n >> V;vector<int> v(n), w(n);//原始数据vector<int> dp(V + 1);//dp表for(int i = 0; i < n; i++)cin >> v[i] >> w[i];//回答第一问//初始化//填表for(int i = 1; i <= n; i++)for(int j = 0; j <= V; j++)if(j - v[i - 1] >= 0) dp[j] = max(dp[j], dp[j - v[i - 1]] + w[i - 1]);cout << dp[V] << endl;//回答第二问//初始化vector<int> dp1(V + 1);for(int j = 1; j <= V; j++) dp1[j] = -1;//填表for(int i = 1; i <= n; i++)for(int j = 0; j <= V; j++)if(j - v[i - 1] >= 0 && dp1[j - v[i - 1]] != -1) dp1[j] = max(dp1[j], dp1[j - v[i - 1]] + w[i - 1]);cout << (dp1[V] == -1 ? 0 : dp1[V]) << endl;return 0;
}

我的思路：

对于第二问，思路其实是差不多的，在这里就简单叙述一下

• 修改状态表示的含义：dp[i][j]表示从i位置之前的数中选体积刚好等于j的物品的所有选择方式的最大价值
• 修改状态转移方程：就是多增加一个条件判断，因为体积刚好等于j的物品的所有选择方式可能是没有的（并不是说他就等于0，而是这个状态根本就不能用），所以我们需要一个新的状态标记一下（-1）如果dp1[i][j - v[i - 1]] != -1我们就不计算；
• 修改初始化：因为体积刚好等于j的物品的所有选择方式可能是没有的，也就是dp[0][j]其中j属于 1~V（表示从 0 位置之前的数中选体积刚好等于 j 的物品的所有选择方式的最大价值，且 j 不为0），这种状态是没有的

对于空间优化：需要与01背包问题的空间优化进行区分

• 填表顺序

  • 01背包的空间优化需要从后往前填表，因为填表时需要用到时上一个表的元素，不能把它先覆盖
  • 完全背包需要用到的是本次填表的上一个数据，而不是上一个表的数据，需要从左往右填表

• 边界条件判断

我的笔记:

• 我的代码之所以不能用memset是因为我的dp数组是一个vector类，并不是一个int类型的数组

• 注意观察一下我的空间优化以及老师的空间优化的区别，这两个都是可以的

零钱兑换

题目链接：

零钱兑换

要点：

• 问题转化：将硬币看作物品，金额看作背包容量，求恰好装满背包的最小物品数
• 初始化技巧：不可达状态用极大值 0x3f3f3f3f 标记，避免干扰 min 操作
• 状态转移：dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i]] + 1)

老师代码：

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

老师思路：

将问题「转化」成我们熟悉的题型。i. 在⼀些物品中「挑选」⼀些出来，然后在满⾜某个「限定条件」下，解决⼀些问题，⼤概率是「背包」模型；ii. 由于每⼀个物品都是⽆限多个的，因此是⼀个「完全背包」问题。接下来的分析就是基于「完全背包」的⽅式来的

我的代码：

错误一：

class Solution {
public:int coinChange(vector<int>& coins, int amount) {int m = coins.size();vector<vector<int>> dp(m + 1, vector<int>(amount + 1));//初始化for(int j = 1; j <= amount; j++) dp[0][j] = -1;//填表for(int i = 1; i <= m; i++){for(int j = 0; j <= amount; j++){dp[i][j] = dp[i - 1][j];if(j - coins[i - 1] >= 0 && dp[i][j - coins[i - 1]] != -1)dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);}}return dp[m][amount];}
};

正确代码：

class Solution {
public:int coinChange(vector<int>& coins, int amount) {int m = coins.size();vector<vector<int>> dp(m + 1, vector<int>(amount + 1));//初始化for(int j = 1; j <= amount; j++) dp[0][j] = 0x3f3f3f3f;//填表for(int i = 1; i <= m; i++){for(int j = 0; j <= amount; j++){dp[i][j] = dp[i - 1][j];if(j - coins[i - 1] >= 0 && dp[i][j - coins[i - 1]] != 0x3f3f3f3f)dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);}}return dp[m][amount] == 0x3f3f3f3f ? -1 : dp[m][amount];}
};

空间优化：

class Solution {
public:int coinChange(vector<int>& coins, int amount) {int m = coins.size();vector<int> dp(amount + 1);//初始化for(int j = 1; j <= amount; j++) dp[j] = 0x3f3f3f3f;//填表for(int i = 1; i <= m; i++){for(int j = 0; j <= amount; j++){if(j - coins[i - 1] >= 0 && dp[j - coins[i - 1]] != 0x3f3f3f3f)dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);}}return dp[amount] == 0x3f3f3f3f ? -1 : dp[amount];}
};

我的思路：

• 初始错误：用 -1 标记不可达状态，导致 min 操作无法正确处理
• 修正后：用 0x3f3f3f3f 标记不可达，最终结果判断是否为该值
• 空间优化时，需注意一维 dp 的遍历顺序和条件判断

我的笔记:

• 使用 unsigned long long 可避免整数溢出（LeetCode 特定用例）

零钱兑换∥

题目链接：

零钱兑换∥

要点：

• 组合数问题：不同顺序视为同一种方案（与排列数区分）
• 状态转移：dp[j] += dp[j - coins[i]]，从前往后遍历
• 初始化：dp[0] = 1（空背包为一种方案）

老师代码：

class Solution
{
public:int change(int amount, vector<int>& coins){vector<unsigned long long> dp(amount + 1); // 建表dp[0] = 1; // 初始化for(auto x : coins) // 拿出物品for(int j = x; j <= amount; j++) // 注意遍历顺序和起始终⽌位置dp[j] += dp[j - x];return dp[amount];}
};

老师思路：

先将问题「转化」成我们熟悉的题型。i. 在⼀些物品中「挑选」⼀些出来，然后在满⾜某个「限定条件」下，解决⼀些问题，⼤概率是背包模型；ii. 由于每⼀个物品都是⽆限多个的，因此是⼀个「完全背包」问题。接下来的分析就是基于「完全背包」的⽅式来的

我的代码：

class Solution {
public:int change(int amount, vector<int>& coins) {int m = coins.size();vector<vector<unsigned long long>> dp(m + 1, vector<unsigned long long>(amount + 1));dp[0][0] = 1;for(int i = 1; i <= m; i++){for(int j = 0; j <= amount; j++){dp[i][j] = dp[i - 1][j];if(j - coins[i - 1] >= 0)dp[i][j] += dp[i][j - coins[i - 1]];}}return dp[m][amount];}
};

空间优化：

class Solution {
public:int change(int amount, vector<int>& coins) {int m = coins.size();vector<unsigned long long> dp(amount + 1);dp[0] = 1;for(int i = 1; i <= m; i++){for(int j = 0; j <= amount; j++){if(j - coins[i - 1] >= 0)dp[j] += dp[j - coins[i - 1]];}}return dp[amount];}
};

我的思路：

我的笔记:

• 逆天题目，现在老师的代码都通不过，需要用unsigned long long 类型才能通过,现在在博客上的是可以通过的代码

完全平方数

题目链接：

完全平方数

要点：

• 问题转化：将完全平方数看作物品，n 看作背包容量，求恰好装满的最小物品数
• 数学优化：只需遍历 j * j <= i 的平方数
• 状态转移：dp[i] = min(dp[i], dp[i - j*j] + 1)

老师代码：

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

老师思路：

这⾥给出⼀个⽤「拆分出相同⼦问题」的⽅式，定义⼀个状态表⽰。（⽤「完全背包」⽅式的解法就仿照之前的分析模式就好啦~~） 为了叙述⽅便，把和为 n 的完全平⽅数的最少数量简称为「最⼩数量」

我的代码：

class Solution {
public:int numSquares(int n) {int m = (int)sqrt(n) + 1;vector<vector<int>> dp(m + 1, vector<int>(n + 1));for(int j = 1; j <= n; j++) dp[0][j] = 0x3f3f3f3f;for(int i = 1; i <= m; i++){for(int j = 0; j <= n; j++){dp[i][j] = dp[i - 1][j];if(j - i * i >= 0) dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1);}}return dp[m][n];}
};

我的思路：

我的笔记:

问题解决注意事项

C++语法：

1. 容器初始化：
   • vector 初始化用构造函数（如 vector<int> dp(n+1, 0x3f3f3f3f)），避免手动循环
   • 二维 vector 初始化：vector<vector<int>> dp(n+1, vector<int>(m+1, 0))
2. 数值溢出：大数问题使用 unsigned long long 或 INF = 0x3f3f3f3f 标记非法状态
3. 遍历顺序：完全背包正序遍历，01背包逆序遍历

算法思路：

1. 状态定义：
   • 明确 dp[i][j] 含义（如“前 i 个物品装满容量 j 的方案数”）
   • 区分“恰好装满”与“不超过容量”的初始化差异
2. 转移方程设计：
   • 完全背包：dp[j] = max(dp[j], dp[j - v[i]] + w[i])（正序）
   • 组合数问题：先物品后容量，避免重复计数
3. 剪枝优化：
   • 完全平方数问题中，内层循环仅需遍历到 sqrt(i)