完全背包理论基础
0-1背包 与 完全背包的区别：
0-1背包：一个物品只能拿一次
完全背包：一个物品可以拿多次
完全背包递推公式跟01背包一直。但遍历顺序不为逆序，而是正序遍历（正序遍历可以实现某个物品取多次）。
function maxValue(weight, value, bagWeight) {
let dp = new Array(bagWeight + 1).fill(0); //初始化
for (let i = 0; i < weight.length; i++) {
//物品
for (let j = weight[i]; j <= bagWeight; j++) {
//背包
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
console.log(dp);
}
return dp[bagWeight];
}
maxValue([1, 3, 4], [15, 20, 30], 4);
// dp数组打印：
// [ 0, 15, 30, 45, 60 ]
// [ 0, 15, 30, 45, 60 ]
// [ 0, 15, 30, 45, 60 ]
零钱兑换
本质：完全背包的应用。装满一个背包有多少种方法（与之前求目标和类似，但是目标和的物品只能选择一次）
力扣题目链接
- 含义及递推公式
dp[j] 装满背包j，有dp[j]种方法
dp[j] += dp[j - coins[i]];
2.正序遍历（因为同一物品可以取多次）
var change = function(amount, coins) {
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];
};
组合总和
leecode题目链接
与零钱兑换的区别：
本题强调元素的顺序，零钱兑换不强调元素顺序。
遍历顺序若为先物品，后背包：得到组合数
先物品，后背包：得到排列数
var combinationSum4 = function(nums, target) {
let dp = new Array(target + 1).fill(0); //初始化
dp[0] = 1;
for (let i = 0; i <= target; i++) {
//背包
for (let j = 0; j < nums.length; j++) {
//物品
if (i - nums[j] >= 0) {
dp[i] += dp[i - nums[j]];
}
}
console.log(dp);
}
console.log(dp[target]);
return dp[target];
};
