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

代码随想录算法训练营Day32| 完全背包问题（二维数组滚动数组）、LeetCode 518 零钱兑换 II、377 组合总数 IV、爬楼梯（进阶）

news 来源：原创 2025/8/25 13:41:59

理论基础

完全背包问题

在完全背包问题中，每种物品都有无限个，我们可以选择任意个数（包括不选），放入一个容量为 $W$ 的背包中。我们希望在不超过容量的情况下，最大化背包内物品的总价值。

完全背包：二维

1. 定义dp数组

dp[i][j] 表示在前 i 种物品中（每种可以无限使用），容量为 j 的背包能取得的最大价值。

2. 状态转移公式

在考虑当前物品 i ，背包容量为 j 时，依旧有两个选择：

不选当前物品 →dp[i - 1][j]
选当前物品 → dp[i][j - w[i]] + v[i]

这里和0-1背包最大的区别就是，0-1背包是根据上一行的值进行状态转移的，而完全背包是从当前行进行状态转移的，因为在后者的语境下物品可以被选择无限次！也就是选了当前物品i之后，还可以再选它。因此转移思路可以写为如下代码：

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

3. 初始化dp数组

因为状态转移需要用到前一行，所以需要初始化选择物品0的情况，能放多少就放多少。

for (int j = weight[0]; j <= bagSize; j++) {dp[0][j] = (j / weight[0]) * value[0]; 
}

4. 代码实践

int completeKnapsack2D(int bagSize, const vector<int>& weight, const vector<int>& value) {int n = weight.size();vector<vector<int>> dp(n, vector<int>(bagSize + 1, 0));for (int j = weight[0]; j <= bagSize; j++) {dp[0][j] = (j / weight[0]) * value[0]; }for (int i = 1; i < n; i++) {for (int j = 0; j <= bagSize; j++) {if (j < weight[i]) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);}}}return dp[n - 1][bagSize];
}

完全背包：一维

可以根据上述的二维数组优化成滚动数组的写法，如下：

int completeKnapsack1D(int bagSize, const vector<int>& weight, const vector<int>& value) {int n = weight.size();vector<int> dp(bagSize + 1, 0);for (int j = weight[0]; j <= bagSize; j++) {dp[j] = (j / weight[0]) * value[0]; }for (int i = 1; i < n; i++) {for (int j = weight[i]; j <= bagSize; j++) {dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}}return dp[bagSize];
}

有一点很重要，这里必须正序遍历！二维完全背包问题的状态转移依赖的值包含了当前行和上一行，我们需要在遍历的时候保证“当前物品可以被重复选择”这一特性。

在一维的方法中，当遍历到容量 j，我们在用 dp[j - weight] 来更新 dp[j] ，而这个 dp[j - weight]，必须是**这一轮已经更新过的结果。**也就是说，它需要我们已经考虑了当前物品被使用过的状态，只有正序遍历可以实现这一点！

我们遍历 j = weight[i] 到 bagSize：

for (int j = weight[i]; j <= bagSize; j++) {dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}

在这个过程中：

dp[j - weight[i]] 是容量更小的状态。
如果 dp[j - weight[i]] 是在这一轮已经被当前物品 i 更新过的，那么这就代表它可能已经放了 1 个、2 个… 当前物品。
现在再放一个当前物品，就相当于「我又放了一个」，这代表我们重复使用了当前物品。

如果是倒序，那么又回到了0-1背包问题：此时dp[j - weight] 是上一轮的旧值，它不包含“选了当前物品的状态”，所以只能选一次，不能重复使用，刚好满足0-1背包的需要。

for (int i = 0; i < n; i++) {for (int j = bagweight; j >= weight[i]; j--) {dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

最后总结一下：完全背包正序遍历时，dp[j - weight[i]] 可能已经包含了当前物品的若干次选择，所以能继续“再来一次”；而倒序时只用旧值，不能重复选择。列了个表格，便于进一步记忆和比较：

特点	0-1 背包	完全背包（unbounded）
每件物品数量	只能选一次	可以选多次（无限）
状态转移	只能用一次的状态	可以重复使用
遍历顺序	`j` 倒序遍历	`j` 正序遍历

题目

力扣 518 零钱兑换 II

本问题是一个组合问题，所以外层遍历物品，内层遍历容量。对于每个金额j，枚举有哪些组合方式能够凑齐这个金额，与顺序无关。代码如下：

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

此外，有两个点，第一是初始化只需要初始化j = 0，组成零也就是都不选择，只有一种写法。第二是vector里的类型，int会溢出，因此写成uint64_t 也就是64位无符号。这里也复习一下：

类型	位数	最大值
`int`	32 位	约 21 亿（2³¹ - 1）
`long long` / `int64_t`	64 位有符号	约 9 × 10¹⁸
`uint64_t`	64 位无符号	约 18 × 10¹⁸（2⁶⁴ - 1）

力扣 377 组合总数 IV

本问题核心是排列，不同的排列方式单独算次数，因此外层遍历容量，内层遍历物品。也就是说对于每一个j，每次都从头开始尝试所有的数，以此得到不同的顺序。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<uint64_t> dp(target + 1, 0);dp[0] = 1;for(int j = 1; j <= target; j++){for(int i = 0; i < nums.size(); i++){if(j >= nums[i]) dp[j] += dp[j - nums[i]];}}return dp[target];}
};

例如dp[j] 中包含了：

dp[j - 1] + 用 1 结尾
dp[j - 2] + 用 2 结尾

这样 [1,2] 和 [2,1] 被视为不同路径，即排列。

总结

外层循环	内层循环	问题	说明
构造方式（物品）	状态容量（目标）	组合	每种构造路径只被考虑一次
状态容量（目标）	构造方式（物品）	排列	对每种状态尝试所有构造顺序

卡码 57 爬楼梯（进阶）AC

本题也是一个排列问题，可以把楼梯总数 $n$ 看作背包容量，将 $[1, m]$ 看作物体的重量，得到代码如下：

#include<iostream>
#include<vector>
using namespace std;int main(){int m, n;while (cin >> n >> m){vector<int> dp(n + 1, 0);dp[0] = 1;for(int j = 1; j <= n; j++){for(int i = 1; i <= m; i++){if(j >= i) dp[j] += dp[j - i];}}cout<<dp[n]<<endl;}return 0;}