01背包理论基础
解法一：
暴力解法：每种物品有取/不取两种状态。
时间复杂度：O(2n)
解法二：
动态规划: 二维数组
- dp[i][j]含义：[0,i]物品，任取，背包容量为j，能取得的最大价值
- 递推公式：两种方式推到至下一步。
- 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)
- 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
-
初始化
观察可知：下一步数值由上一行的数值得到；因此，i=0，一定要初始化
image.png
dp[i][0]，均为0，因为背包容量为0
dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。 - 确定遍历顺序
同样根据上图，可知，先遍历背包，或先遍历物品均可
// weight 物品重量
// value 物品价值
// volumn 背包容量
function maxValue(weight, value, volumn) {
let n = weight.length; //物品个数
let dp = new Array(n).fill(0).map((ele) => {
return new Array(volumn + 1).fill(0);
});
// 初始化
for (let j = 0; j <= volumn; j++) {
dp[0][j] = value[0];
}
for (let i = 0; i < n; i++) {
dp[i][0] = 0;
}
for (let i = 1; i < n; i++) {
for (let j = 1; j <= volumn; j++) {
if (j - weight[i] < 0) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j]);
}
}
}
// 打印
for (let i = 0; i < n; i++) {
let str = "";
for (let j = 0; j <= volumn; j++) {
str += dp[i][j] + " ";
}
console.log(str);
}
return dp[i][j]
}
// test
maxValue([1, 3, 4], [15, 20, 30], 4);
// 结果
// 0 15 15 15 15
// 0 15 15 20 35
// 0 15 15 20 35
解法三：动态规划：一维dp数组
- dp数组含义dp[i]：容量为i的背包的最大价值
- 递推公式：dp[i]=max( dp[i],dp[i-Wi-1]+Vi)
- 初始化：dp均为0
- 遍历顺序：只能先物品后背包，背包为倒序
倒序原因：dp数组是重复利用的。且因为在二维数组中，dp[i][j]是依据上一行的左边推导出来的，所以一维数组应该从右向左（倒序）遍历。倒序才能真的拿到原来左侧的旧值
function maxValue2(weight, value, volumn) {
let n = weight.length; //物品数量
let dp = new Array(volumn + 1).fill(0);
for (let i = 0; i < n; i++) {
for (let j = volumn; j >= 0; j--) {
if (j - weight[i] >= 0) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
}
console.log(dp); //[ 0, 15, 15, 20, 35 ]
return dp[volumn]
}
maxValue2([1, 3, 4], [15, 20, 30], 4);
分割等和求子集
力扣题目
本质：01背包的应用。将子集看作是物品，物品的重量与价值均为元素的值，看其是否能找到dp[num]===target/2
递推公式：
dp[j]=max(dp[j],dp[j-num[i]]+num[i])
初始化：
dp均为0。
var canPartition = function(nums) {
let sum = nums.reduce((p, c) => {
return p + c;
}, 0);
if (sum % 2 !== 0) {
return false;
}
let volumn = sum / 2; //背包容量
let n = nums.length; //物品个数
let dp = new Array(volumn + 1).fill(0);//初始化
for (let i = 0; i < n; i++) {
for (let j = volumn; j >= 0; j--) {
if (j - nums[i] >= 0) {
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
}
return dp[volumn] === sum / 2;
};
目标和
力扣题目链接
分析：背包问题的应用
其实是求装满有几种方法，是一个组合问题。
转换为背包问题：
假设加法的总和为x，那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = target
x = (target + sum) / 2
此时问题就转化为，装满容量为x的背包，有几种方法。
- dp数组含义：装满容量为j（包括j）的包，有dp[j]种方法
- 递推公式：dp[j] += dp[j - nums[i]]
(补充：所以求组合类问题的公式，都是类似这种递推公式） - 初始化：
dp[0]=1
例如：需带入例子。数组[0] ，target = 0，那么 bagSize = (target + sum) / 2 = 0
var findTargetSumWays = function(nums, target) {
let sum=nums.reduce((p,c)=>p+c)
if(Math.abs(target) > sum) {
return 0;
}
if((target + sum) % 2) {
return 0;
}
let bagSize= Math.floor((sum+target)/2)
let dp=new Array(bagSize+1).fill(0)
dp[0]=1
for(let i=0;i<nums.length;i++){
for(let j=bagSize;j>=nums[i];j--){
dp[j] += dp[j-nums[i]]
}
}
return dp[bagSize]
};
