01背包理論基礎(chǔ)
解法一：
暴力解法：每種物品有取/不取兩種狀態(tài)。
時(shí)間復(fù)雜度：O(2n)
解法二：
動(dòng)態(tài)規(guī)劃: 二維數(shù)組
- dp[i][j]含義：[0,i]物品抓艳，任取，背包容量為j帚戳，能取得的最大價(jià)值
- 遞推公式：兩種方式推到至下一步玷或。
- 不放物品i：由dp[i - 1][j]推出，即背包容量為j片任，里面不放物品i的最大價(jià)值偏友，此時(shí)dp[i][j]就是dp[i - 1][j]。(其實(shí)就是當(dāng)物品i的重量大于背包j的重量時(shí)蚂踊，物品i無法放進(jìn)背包中约谈，所以被背包內(nèi)的價(jià)值依然和前面相同。)
- 放物品i：由dp[i - 1][j - weight[i]]推出犁钟，dp[i - 1][j - weight[i]] 為背包容量為j - weight[i]的時(shí)候不放物品i的最大價(jià)值棱诱，那么dp[i - 1][j - weight[i]] + value[i] （物品i的價(jià)值），就是背包放物品i得到的最大價(jià)值
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
-
初始化
觀察可知：下一步數(shù)值由上一行的數(shù)值得到涝动；因此迈勋，i=0，一定要初始化
image.png
dp[i][0]醋粟，均為0靡菇，因?yàn)楸嘲萘繛?
dp[0][j]，即：i為0米愿，存放編號(hào)0的物品的時(shí)候厦凤，各個(gè)容量的背包所能存放的最大價(jià)值。 - 確定遍歷順序
同樣根據(jù)上圖育苟，可知较鼓，先遍歷背包，或先遍歷物品均可
// weight 物品重量
// value 物品價(jià)值
// volumn 背包容量
function maxValue(weight, value, volumn) {
let n = weight.length; //物品個(gè)數(shù)
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);
// 結(jié)果
// 0 15 15 15 15
// 0 15 15 20 35
// 0 15 15 20 35
解法三：動(dòng)態(tài)規(guī)劃：一維dp數(shù)組
- dp數(shù)組含義dp[i]：容量為i的背包的最大價(jià)值
- 遞推公式：dp[i]=max( dp[i],dp[i-Wi-1]+Vi)
- 初始化：dp均為0
- 遍歷順序：只能先物品后背包违柏，背包為倒序
倒序原因：dp數(shù)組是重復(fù)利用的博烂。且因?yàn)樵诙S數(shù)組中，dp[i][j]是依據(jù)上一行的左邊推導(dǎo)出來的漱竖，所以一維數(shù)組應(yīng)該從右向左（倒序）遍歷禽篱。倒序才能真的拿到原來左側(cè)的舊值
function maxValue2(weight, value, volumn) {
let n = weight.length; //物品數(shù)量
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);
分割等和求子集
力扣題目
本質(zhì)：01背包的應(yīng)用。將子集看作是物品馍惹，物品的重量與價(jià)值均為元素的值躺率，看其是否能找到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; //物品個(gè)數(shù)
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;
};
目標(biāo)和
力扣題目鏈接
分析：背包問題的應(yīng)用
其實(shí)是求裝滿有幾種方法，是一個(gè)組合問題肥照。
轉(zhuǎn)換為背包問題：
假設(shè)加法的總和為x脚仔，那么減法對(duì)應(yīng)的總和就是sum - x。
所以我們要求的是 x - (sum - x) = target
x = (target + sum) / 2
此時(shí)問題就轉(zhuǎn)化為舆绎，裝滿容量為x的背包，有幾種方法们颜。
- dp數(shù)組含義：裝滿容量為j（包括j）的包吕朵，有dp[j]種方法
- 遞推公式：dp[j] += dp[j - nums[i]]
(補(bǔ)充：所以求組合類問題的公式，都是類似這種遞推公式） - 初始化：
dp[0]=1
例如：需帶入例子窥突。數(shù)組[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]
};
