完全背包
理解什么是完全背包。和01背包的不同就是每个物品都有无限个。
1.由于每个物品都有无限个，因此遍历容量时，我们不能反向遍历。
2.由于遍历背包容量时，从0开始，所以定义dp数组的大小为容量加1。
#include <iostream>
#include <vector>
using namespace std;
void test_CompletePack(vector<int> weight, vector<int> value, int bagWeight) {
vector<int> dp(bagWeight + 1, 0);
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]);
}
}
cout << dp[bagWeight] << endl;
}
int main() {
int N, V;
cin >> N >> V;
vector<int> weight;
vector<int> value;
for (int i = 0; i < N; i++) {
int w;
int v;
cin >> w >> v;
weight.push_back(w);
value.push_back(v);
}
test_CompletePack(weight, value, V);
return 0;518. 零钱兑换 II
这题不是单纯计算容量内的最大价值，而是恰好装满的情况，有点类似排列组合问题。组合不强调元素之间的顺序，排列强调元素之间的顺序。
1.初始化为dp[0]=1,不然后面的值都为0
2.遍历顺序很重要
*********************************
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
*********************************
本题求的是组合数，所以先物品后背包容量。
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. 组合总和 Ⅳ
与上面那题不一样，这题寻找的是排列，所以遍历顺序是先背包再物品。
1.初始化dp[0]=1,不然后面的值都为0
2.if(j - nums[i] >= 0 && dp[j] < INT_MAX - dp[j - nums[i]] )这个条件很重要，首先我们的背包容量必须大于该物品的大小，另外C++测试用例有两个数相加超过int的数据，所以需要在if里加上dp[i] < INT_MAX - dp[i - num]。
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target+1,0);
dp[0]=1;
for(int j=0;j<=target;j++){
for(int i=0;i<nums.size();i++){
if(j - nums[i] >= 0 && dp[j] < INT_MAX - dp[j - nums[i]] ) dp[j]+=dp[j-nums[i]];
}
}
return dp[target];
}
};70. 爬楼梯 （进阶）
排列问题，先背包再物品，同上题一样的。 记住条件背包容量必须大于该物品的大小。
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n,m;
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(i <= j) dp[j]+=dp[j-i];
}
}
cout << dp[n];
return 0;
}
