day44
完全背包
卡码网：携带研究材料（第七期模拟笔试）
动态规划
思路
完全背包，物品可以无限次取，正序遍历。
复杂度分析
时间复杂度：O(N^2)。
空间复杂度：O(N)。
代码实现
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
/*
给j的容量可重复选择的最大价值为dp[j]
dp[j] = max(dp[j],dp[j-weight[i]] + value[i])
初始化为0
先物品后背包，正序（先背包后物品也行，但是要正序）
*/
int main(){
int N = 0; // item types
int V = 0; // opacity
cin>>N;
cin>>V;
vector<int> weight(N,0);
vector<int> value(N,0);
vector<int> dp(V+1,0);
for(int i = 0;i < N;i++){
cin>>weight[i];
cin>>value[i];
}
for(int i = 0;i < N;i++){
for(int j = 1;j <= V;j++){
if(j >= weight[i]){ // 装得下的时候才尝试更新
dp[j] = max(dp[j],dp[j-weight[i]] + value[i]);
}
}
}
cout<<dp[V];
return 0;
}
零钱兑换Ⅱ
leetcode：518. 零钱兑换 II
动态规划
思路
复杂度分析
时间复杂度：O(N^2)。
空间复杂度：O(N)。
代码实现
C++:
class Solution {
public:
/*
装满j的空间，物品重复去取，总共有dp[j]种方法
dp[j] += dp[j-coins[i]]
初始化为0
先背包再物品，正序
*/
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];
}
};
TS:
/**
物品重复取装满容量j的背包，总共有dp[j]种方法
dp[j] += dp[j - coins[i]];
dp[0] = 1 其余为0
先物品后背包，正序
*/
function change(amount: number, coins: number[]): number {
let dp = new Array(amount+1).fill(0);
dp[0] = 1;
for(let i = 0;i < coins.length;i++){
for(let j = coins[i];j <= amount;j++){
dp[j] += dp[j-coins[i]];
}
}
return dp[amount];
};
组合总和Ⅳ
leetcode：377. 组合总和 Ⅳ
动态规划
注意点
- 物品一定要完整遍历（和组合不一样，组合有时可以剪枝）
代码实现
/**
物品取无限次，装满容量为j的背包，总共有dp[j]种方法
dp[j] += dp[j - nums[i]];
dp[0] = 1;其余为0
排列，所以先背包再物品，正序
*/
function combinationSum4(nums: number[], target: number): number {
const dp:number[] = new Array(target+1).fill(0);
dp[0] = 1;
for(let j = 1;j <= target;j++){ // 背包
for(let i = 0;i < nums.length;i++){ // 物品
if(j >= nums[i]) dp[j] += dp[j - nums[i]];
}
}
return dp[target];
};