与人妖做视频网站/百度经验官网

理论基础

完全背包问题

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

完全背包：二维

1. 定义dp数组

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

2. 状态转移公式

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

1. 不选当前物品 →dp[i - 1][j]
2. 选当前物品 → 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]] 可能已经包含了当前物品的若干次选择，所以能继续“再来一次”；而倒序时只用旧值，不能重复选择。列了个表格，便于进一步记忆和比较：

题目

力扣 518 零钱兑换 II

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

力扣 377 组合总数 IV

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

总结

卡码 57 爬楼梯（进阶）AC

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