「背包問(wèn)?題：給你一個(gè)可裝載重量為W的背包和N個(gè)物品，每個(gè)物品有重量和價(jià)值兩個(gè)屬性。其中第i個(gè)物品的重量為wt[i]，價(jià)值為val[i]，現(xiàn)在讓你用這個(gè)背包裝物品，最多能裝的價(jià)值是多少？」

今天是十五周算法訓(xùn)練營(yíng)的第十三周，主要講背包問(wèn)題專(zhuān)題。（歡迎加入十五周算法訓(xùn)練營(yíng)，與小伙伴一起卷算法）

「背包問(wèn)題：給你一個(gè)可裝載重量為W的背包和N個(gè)物品，每個(gè)物品有重量和價(jià)值兩個(gè)屬性。其中第i個(gè)物品的重量為wt[i]，價(jià)值為val[i]，現(xiàn)在讓你用這個(gè)背包裝物品，最多能裝的價(jià)值是多少？」

(資料圖片)

0-1背包動(dòng)態(tài)規(guī)劃思路

明確狀態(tài)和選擇

狀態(tài)有兩個(gè)：背包的容量和可選擇的物品

選擇就是：裝進(jìn)背包或者不裝進(jìn)背包

dp數(shù)組的含義

剛才明確了狀態(tài)，現(xiàn)在需要用dp數(shù)組把狀態(tài)表達(dá)出來(lái)，剛才找到的「狀態(tài)」，有兩個(gè)，也就是說(shuō)我們需要一個(gè)二維dp數(shù)組，一維表示可選擇的物品，一維表示背包的容量。

dp[i][w]表示的就是對(duì)于[0……i]個(gè)物品，當(dāng)前背包容量為w時(shí)的最大價(jià)值

根據(jù)選擇，思考狀態(tài)轉(zhuǎn)移的邏輯

dp[i][w]表示：對(duì)于前i個(gè)物品，當(dāng)前背包的容量為w時(shí)，這種情況下可以裝下的最大價(jià)值是dp[i][w]。

如果你沒(méi)有把這第i個(gè)物品裝入背包，那么很顯然，最大價(jià)值dp[i][w]應(yīng)該等于dp[i-1][w]。你不裝嘛，那就繼承之前的結(jié)果。

如果你把這第i個(gè)物品裝入了背包，那么dp[i][w]應(yīng)該等于dp[i-1][w-wt[i-1]] + val[i-1]。

首先，由于i是從 1 開(kāi)始的，所以對(duì)val和wt的取值是i-1。

明確base case: 此處的base case就是dp[ 0 ][ …… ]和dp[……][0]的時(shí)候，這個(gè)時(shí)候沒(méi)有物品或者背包沒(méi)有容量，此時(shí)價(jià)值為0

背包問(wèn)題動(dòng)態(tài)規(guī)劃的結(jié)構(gòu)

for 狀態(tài)1 in 狀態(tài)1的所有取值：    for 狀態(tài)2 in 狀態(tài)2的所有取值：        for ...            dp[狀態(tài)1][狀態(tài)2][...] = 擇優(yōu)(選擇1，選擇2...)

0-1背包解題思路

/** * 0-1背包問(wèn)題解題思路 *  * 給你一個(gè)可裝載重量為W的背包和N個(gè)物品，每個(gè)物品有重量和價(jià)值兩個(gè)屬性。其中第i個(gè)物品的重量為wt[i]，價(jià)值為val[i]，現(xiàn)在讓你用這個(gè)背包裝物品，最多能裝的價(jià)值是多少？ */// 該問(wèn)題是一個(gè)典型的動(dòng)態(tài)規(guī)劃問(wèn)題// 1. 明確狀態(tài)和選擇// 狀態(tài)就是背包的容量和可選的物品// 選擇就是要不要裝該物品// 2. dp數(shù)組含義// dp[i][w]表示前i個(gè)物品、當(dāng)前背包容量為w時(shí)，能裝的最大價(jià)值// 3. 狀態(tài)轉(zhuǎn)移邏輯// 為了獲取dp[i][w]的時(shí)候需要考慮當(dāng)前要放入物品的重量是否可以放到背包中，即比較當(dāng)前背包容量和要放入物品重量// 若不能放進(jìn)去:dp[i][w] = dp[i - 1][w]// 若可以放進(jìn)去,則此時(shí)就需要比較放入和不放入后的價(jià)值dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - wtPresent] + valPresent)function knapsack(W, N, wt, val) {    // 定義dp    const dp = new Array(N + 1);    for (let i = 0; i < dp.length; i++) {        dp[i] = (new Array(W + 1)).fill(0);    }    // base case    // 當(dāng)在定義dp的時(shí)候已經(jīng)進(jìn)行了初始化為0，0就是起base case    for (let i = 1; i < dp.length; i++) {        for (let w = 1; w < dp[0].length; w++) {            // 判斷當(dāng)前物品是否可以放到背包中，如果不能放進(jìn)去            if (w - wt[i - 1] < 0) {                dp[i][w] = dp[i - 1][w];            } else {                // 如果可以放進(jìn)去                dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);            }        }    }    // 最終結(jié)果    return dp[N][W];}

分割等和子集

給你一個(gè) 只包含正整數(shù) 的 非空 數(shù)組 nums 。請(qǐng)你判斷是否可以將這個(gè)數(shù)組分割成兩個(gè)子集，使得兩個(gè)子集的元素和相等。

示例 1：

輸入：nums = [1,5,11,5] 輸出：true 解釋?zhuān)簲?shù)組可以分割成 [1, 5, 5] 和 [11] 。

// 對(duì)于經(jīng)典背包問(wèn)題，是給你一個(gè)可裝載重量為W的背包和N個(gè)物品，每個(gè)物品有重量和價(jià)值兩個(gè)屬性。其中第i個(gè)物品的重量為wt[i]，價(jià)值為val[i]，現(xiàn)在讓你用這個(gè)背包裝物品，最多能裝的價(jià)值是多少？// 該問(wèn)題其實(shí)是經(jīng)典背包問(wèn)題的變形，可以先對(duì)集合求和，得出sum,該問(wèn)題就可以轉(zhuǎn)換為背包問(wèn)題：// 給一個(gè)可裝載重量為sum / 2的背包和N個(gè)物品，每個(gè)物品的重量為nums[i],現(xiàn)在讓你裝物品，是否存在一種裝法，能夠恰好將背包裝滿(mǎn)// 1. 明確狀態(tài)和選擇// 狀態(tài)就是背包容量和可選擇的物品// 選擇就是裝進(jìn)背包和不裝進(jìn)背包// 2. dp數(shù)組函數(shù)// dp[i][j] = x表示，對(duì)于前i個(gè)物品，當(dāng)前背包的容量為j時(shí)，若x為true，則說(shuō)明可以恰好將背包裝滿(mǎn)，若x為false，則說(shuō)明不能恰好將背包裝滿(mǎn)。// 3. 狀態(tài)轉(zhuǎn)移邏輯// 若放不進(jìn)去，dp[i][j] = dp[i - 1][j]// 若能夠放進(jìn)去dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]// 4. base case// base case就是：// (1)有物品但是容量為0,肯定能裝滿(mǎn)，此時(shí)即dp[……][0] = true// (2)沒(méi)有物品但是有容量時(shí)，肯定裝不滿(mǎn)，此時(shí)即dp[0][……] = falsefunction canPartition(nums) {    let sums = 0;    nums.forEach(num => sums += num);    // 如果是奇數(shù)，不能被劃分，直接返回false    if (sums % 2 === 1) {        return false;    }    const numsLen = nums.length;    const dp = new Array(numsLen + 1);    for (let i = 0; i < dp.length; i++) {        dp[i] = (new Array(sums / 2 + 1)).fill(false);    }    // base case    for (let i = 0; i < dp.length; i++) {        dp[i][0] = true;    }    for (let i = 1; i < dp.length; i++) {        for (let j = 1; j < dp[0].length; j++) {            if (j - nums[i - 1] < 0) {                dp[i][j] = dp[i - 1][j];            } else {                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];            }        }    }    // 最終其dp[n][sum / 2]就是起結(jié)果,因?yàn)榇藭r(shí)能找到和的一半，另一半也是和的一半    return dp[numsLen][sums / 2];}

零錢(qián)兌換II

給你一個(gè)整數(shù)數(shù)組 coins 表示不同面額的硬幣，另給一個(gè)整數(shù) amount 表示總金額。

請(qǐng)你計(jì)算并返回可以湊成總金額的硬幣組合數(shù)。如果任何硬幣組合都無(wú)法湊出總金額，返回 0 。

假設(shè)每一種面額的硬幣有無(wú)限個(gè)。

題目數(shù)據(jù)保證結(jié)果符合 32 位帶符號(hào)整數(shù)。

示例 1：

輸入：amount = 5, coins = [1, 2, 5] 輸出：4 解釋?zhuān)河兴姆N方式可以湊成總金額： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1

// 該問(wèn)題可轉(zhuǎn)換為有一個(gè)背包，最大容量為amount，有一系列物品coins，每個(gè)物品的重量為coins[i]，每個(gè)物品的數(shù)量無(wú)限。請(qǐng)問(wèn)有多少種方法，能夠把背包恰好裝滿(mǎn)？// 與經(jīng)典背包區(qū)別的是每個(gè)物品的數(shù)量是無(wú)限的，這也就是完全背包問(wèn)題。// 1. 狀態(tài)和選擇// 狀態(tài)：背包的容量和可選擇的物品// 選擇：放進(jìn)背包和不放進(jìn)背包// 2. 定義dp// dp[i][j]:若只使用前i個(gè)物品，當(dāng)背包容量為j時(shí)，有dp[i][j]種方法可以裝滿(mǎn)背包。換句話說(shuō)：若只使用coins中的前i個(gè)硬幣的面值，若想湊出金額j，有dp[i][j]中湊法// 3. 狀態(tài)轉(zhuǎn)移邏輯// 若不能放進(jìn)去：dp[i][j] = dp[i - 1][j]// 若能夠放進(jìn)去：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - coins[i]]// 4. base case// (1)有硬幣，但是目標(biāo)結(jié)果為0，即dp[0……n][0] = 1// (2)沒(méi)有硬幣，即dp[0][0……n] = 0function change(amount, coins) {    const n = coins.length;    const dp = new Array(n + 1);    for (let i = 0; i < dp.length; i++) {        dp[i] = (new Array(amount + 1)).fill(0);    }    // base case    for (let i = 0; i < dp.length; i++) {        dp[i][0] = 1;    }    // 遍歷dp    for (let i = 1; i < dp.length; i++) {        for (let j = 1; j < dp[0].length; j++) {            // 如果當(dāng)前硬幣不能放進(jìn)背包            if (j < coins[i - 1]) {                dp[i][j] = dp[i - 1][j];            } else {                // 能放進(jìn)去，則結(jié)果就是放進(jìn)去與不放進(jìn)去的加和                // 為什么當(dāng)放進(jìn)去的時(shí)候?yàn)閕，因?yàn)榇藭r(shí)已經(jīng)決定使用coins[i - 1]的值                dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];            }        }    }    // 目標(biāo)結(jié)果就是[N, amount]    return dp[n][amount];}// 通過(guò)觀察發(fā)現(xiàn)dp[i][j]之和dp[i][……]和dp[i - 1][……]相關(guān)// 則可進(jìn)行狀態(tài)壓縮function change1(amount, coins) {    // 定義dp    const dp = (new Array(amount + 1)).fill(0);    // base case    dp[0] = 1;    // 進(jìn)行遍歷    for (let i = 0; i < coins.length; i++) {        for (let j = 1; j < dp.length; j++) {            if (j >= coins[i]) {                dp[j] = dp[j] + dp[j - coins[i]];            }        }    }    return dp[dp.length - 1];}const amount = 5;const coins = [1, 2, 5];console.log(change1(amount, coins));

最后一塊石頭的重量II

有一堆石頭，用整數(shù)數(shù)組 stones 表示。其中 stones[i] 表示第 i 塊石頭的重量。

每一回合，從中選出任意兩塊石頭，然后將它們一起粉碎。假設(shè)石頭的重量分別為 x 和 y，且 x <= y。那么粉碎的可能結(jié)果如下：

如果 x == y，那么兩塊石頭都會(huì)被完全粉碎； 如果 x != y，那么重量為 x 的石頭將會(huì)完全粉碎，而重量為 y 的石頭新重量為 y-x。 最后，最多只會(huì)剩下一塊 石頭。返回此石頭 最小的可能重量 。如果沒(méi)有石頭剩下，就返回 0。

示例 1：

輸入：stones = [2,7,4,1,8,1] 輸出：1 解釋?zhuān)?組合 2 和 4，得到 2，所以數(shù)組轉(zhuǎn)化為 [2,7,1,8,1]， 組合 7 和 8，得到 1，所以數(shù)組轉(zhuǎn)化為 [2,1,1,1]， 組合 2 和 1，得到 1，所以數(shù)組轉(zhuǎn)化為 [1,1,1]， 組合 1 和 1，得到 0，所以數(shù)組轉(zhuǎn)化為 [1]，這就是最優(yōu)值。

// 該問(wèn)題和分割等和子集問(wèn)題（416）處理方式類(lèi)似，就是背包問(wèn)題// 1. 狀態(tài)和選擇// 狀態(tài)：背包和當(dāng)前可選物品// 選擇：是否裝進(jìn)背包// 2. dp數(shù)組含義// dp[w][i]表示背包容量為w時(shí)，前i個(gè)物品，最多能夠裝的物品重量// 3. 狀態(tài)轉(zhuǎn)移邏輯// 不能裝進(jìn)去：dp[w][i] = dp[w][i - 1]// 能夠裝進(jìn)去：dp[w][i] = Math.max(dp[w][i - 1], dp[w - stones[i]][i - 1] + stones[i])// 4. base case// 當(dāng)i = 0時(shí)，dp[0……w][0] = 0// 當(dāng)w = 0時(shí)，dp[0][……] = 0function lastStoneWeightII(stones) {    // 得到總重量    let sum = 0;    stones.forEach(stone => {        sum += stone;    });    const weight = Math.floor(sum / 2);    // 定義dp    const dp = new Array(weight + 1);    for (let i = 0; i < dp.length; i++) {        dp[i] = (new Array(stones.length + 1)).fill(0);    }    // base case 在初始化時(shí)已經(jīng)完成    // 循環(huán)遍歷    for (let w = 1; w < dp.length; w++) {        for (let i = 1; i < dp[0].length; i++) {            // 判斷是否可以裝進(jìn)去            if (w - stones[i - 1] < 0) {                dp[w][i] = dp[w][i - 1];            } else {                dp[w][i] = Math.max(dp[w][i - 1], dp[w - stones[i - 1]][i - 1] + stones[i - 1]);            }        }    }    return sum - 2 * dp[weight][stones.length];}const stones = [31,26,33,21,40];console.log(lastStoneWeightII(stones));

目標(biāo)和

給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) target 。

向數(shù)組中的每個(gè)整數(shù)前添加 ‘+’ 或 ‘-‘ ，然后串聯(lián)起所有整數(shù)，可以構(gòu)造一個(gè) 表達(dá)式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串聯(lián)起來(lái)得到表達(dá)式 “+2-1” 。 返回可以通過(guò)上述方法構(gòu)造的、運(yùn)算結(jié)果等于 target 的不同 表達(dá)式 的數(shù)目。

示例 1：

輸入：nums = [1,1,1,1,1], target = 3 輸出：5 解釋?zhuān)阂还灿?5 種方法讓最終目標(biāo)和為 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 – 1 + 1 + 1 + 1 = 3 +1 + 1 – 1 + 1 + 1 = 3 +1 + 1 + 1 – 1 + 1 = 3 +1 + 1 + 1 + 1 – 1 = 3

// 該方法可以用背包解決// 如何轉(zhuǎn)換為01背包問(wèn)題呢？// 假設(shè)加法的總和為x，那么減法對(duì)應(yīng)的總和就是sum - x// 所以我們要求的就是x - (sum - x) = S// x = (S + sum) / 2// 此時(shí)問(wèn)題就轉(zhuǎn)化為：裝滿(mǎn)容量為x背包，有幾種方法// 1. 狀態(tài)和選擇// 2. dp數(shù)組含義// dp[i][w]：前i個(gè)物品、背包容量為w時(shí)，有幾種方式裝滿(mǎn)// 3. 狀態(tài)轉(zhuǎn)移邏輯// 裝不進(jìn)去：dp[i][w] = dp[i - 1][w]// 能裝進(jìn)去：dp[i][w] = dp[i - 1][w - nums[i]] + dp[i - 1][w]// 4. base case// dp[0][0] = 1function findTargetSumWays(nums, target) {    // 求和    const sum = nums.reduce((total, num) => total + num);    // weight必須大于0且為整數(shù)    if (target + sum < 0 || (target + sum) % 2 === 1) {        return 0;    }    // 求weight    const weight = (target + sum) / 2;    // dp    const dp = new Array(nums.length + 1);    for (let i = 0; i < dp.length; i++) {        dp[i] = (new Array(weight + 1)).fill(0);    }    // base case    dp[0][0] = 1;    // 循環(huán)    for (let i = 1; i < dp.length; i++) {        for (let w = 0; w < dp[i].length; w++) {            // 不能裝進(jìn)去            if (w - nums[i - 1] >= 0) {                dp[i][w] = dp[i - 1][w] + dp[i - 1][w - nums[i - 1]];            } else {                dp[i][w] = dp[i - 1][w];            }        }    }    return dp[nums.length][weight];}// 用回溯算法實(shí)現(xiàn)一遍function findTargetSumWays1(nums, target) {    let result = 0;    const backtrack = (index, sum) => {        // 結(jié)束條件        if (index === nums.length) {            if (sum === target) {                result++;            }            return;        }        backtrack(index + 1, sum + nums[index]);        backtrack(index + 1, sum - nums[index]);    };    backtrack(0, 0);    return result;}const nums = [0, 0, 0, 1];const target = 1;console.log(findTargetSumWays1(nums, target));