完全背包
完全背包中，每件物品都有无数件；这主要影响了遍历背包容量时的遍历顺序，应该从小到大去遍历，这样才能包括有多件相同物品的情况。
思路
先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}
先遍历背包，再遍历物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量for(int i = 0; i < weight.size(); i++) { // 遍历物品if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}
代码随想录
# include <bits/stdc++.h>using namespace std;int main() {int N, V;cin >> N >> V; vector<int>weight;vector<int>value;for (int i = 0; i < N; i++) {int w, v;cin >> w >> v;weight.push_back(w);value.push_back(v);}vector<int> dp(V + 1, 0);for (int i = 0; i < weight.size(); i++) {for (int j = weight[i]; j <= V; j++) {dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[V] << endl;return 0;
}
518. 零钱兑换 II
思路
- 组合个数问题，使用递推公式 ：
dp[j] += dp[j - nums(i)]。
代码随想录
class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> 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. 组合总和 Ⅳ
思路
- 组合不强调顺序，外层
for循环遍历物品，内层for循环遍历背包 - 排列强调顺序， 外层
for循环遍历背包， 内层for循环遍历物品。 - 本题虽然叫组合总和，但是看示例1，还是对顺序有要求的。
代码随想录
class Solution {
public:int combinationSum4(vector<int>& nums, int target) {sort(nums.begin(), nums.end());vector<int> dp(target + 1, 0);dp[0] = 1;for (int i = 0; i <= target; i++) {for (int j = 0; j < nums.size(); j++) {// 这里的超出限制很少见啊if (i - nums[j] >= 0 && dp[i] < INT32_MAX - dp[i - nums[j]] ) {dp[i] += dp[i - nums[j]];}}}return dp[target];}
};
70. 爬楼梯 （进阶）
思路
- 把能跨的步数堪看成物品，总共有
m件物品，放满容量为n的背包（台阶）。 - 记录次数的递推公式均为
dp[i] += dp[i - nums[j]]的形式。 - 本题是排列，因此先遍历背包。
代码随想录
# include <bits/stdc++.h>using namespace std;int main() {int n, m;cin >> n >> m;vector<int> dp(n + 1, 0);dp[0] = 1;for (int i = 1; i <= n; i ++) {for (int j = 1; j <= m; j++) {if (i - j >= 0) dp[i] += dp[i - j];}}cout << dp[n]<< endl;return 0;
}
