聊聊十五周算法訓練營——背包問題
今天是十五周算法訓練營的第十三周，主要講背包問題專題。（歡迎加入十五周算法訓練營，與小伙伴一起卷算法）
「背包問題：給你一個可裝載重量為W的背包和N個物品，每個物品有重量和價值兩個屬性。其中第i個物品的重量為wt[i]，價值為val[i]，現在讓你用這個背包裝物品，最多能裝的價值是多少？」
0-1背包動態規劃思路
明確狀態和選擇
狀態有兩個：背包的容量和可選擇的物品
選擇就是：裝進背包或者不裝進背包
dp數組的含義
剛才明確了狀態，現在需要用dp數組把狀態表達出來，剛才找到的「狀態」，有兩個，也就是說我們需要一個二維dp數組，一維表示可選擇的物品，一維表示背包的容量。
dp[i][w]表示的就是對于[0……i]個物品，當前背包容量為w時的最大價值
根據選擇，思考狀態轉移的邏輯
dp[i][w]表示：對于前i個物品，當前背包的容量為w時，這種情況下可以裝下的最大價值是dp[i][w]。
如果你沒有把這第i個物品裝入背包，那么很顯然，最大價值dp[i][w]應該等于dp[i-1][w]。你不裝嘛，那就繼承之前的結果。
如果你把這第i個物品裝入了背包，那么dp[i][w]應該等于dp[i-1][w-wt[i-1]] + val[i-1]。
首先，由于i是從 1 開始的，所以對val和wt的取值是i-1。
明確base case: 此處的base case就是dp[ 0 ][ …… ]和dp[……][0]的時候，這個時候沒有物品或者背包沒有容量，此時價值為0
背包問題動態規劃的結構
for 狀態1 in 狀態1的所有取值：
for 狀態2 in 狀態2的所有取值：
for ...
dp[狀態1][狀態2][...] = 擇優(選擇1，選擇2...)0-1背包解題思路
/**
* 0-1背包問題解題思路
*
* 給你一個可裝載重量為W的背包和N個物品，每個物品有重量和價值兩個屬性。其中第i個物品的重量為wt[i]，價值為val[i]，現在讓你用這個背包裝物品，最多能裝的價值是多少？
*/
// 該問題是一個典型的動態規劃問題
// 1. 明確狀態和選擇
// 狀態就是背包的容量和可選的物品
// 選擇就是要不要裝該物品
// 2. dp數組含義
// dp[i][w]表示前i個物品、當前背包容量為w時，能裝的最大價值
// 3. 狀態轉移邏輯
// 為了獲取dp[i][w]的時候需要考慮當前要放入物品的重量是否可以放到背包中，即比較當前背包容量和要放入物品重量
// 若不能放進去:dp[i][w] = dp[i - 1][w]
// 若可以放進去,則此時就需要比較放入和不放入后的價值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
// 當在定義dp的時候已經進行了初始化為0，0就是起base case
for (let i = 1; i < dp.length; i++) {
for (let w = 1; w < dp[0].length; w++) {
// 判斷當前物品是否可以放到背包中，如果不能放進去
if (w - wt[i - 1] < 0) {
dp[i][w] = dp[i - 1][w];
} else {
// 如果可以放進去
dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
}
}
}
// 最終結果
return dp[N][W];
}分割等和子集
給你一個 只包含正整數 的 非空 數組 nums 。請你判斷是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。
示例 1：
輸入：nums = [1,5,11,5] 輸出：true 解釋：數組可以分割成 [1, 5, 5] 和 [11] 。
// 對于經典背包問題，是給你一個可裝載重量為W的背包和N個物品，每個物品有重量和價值兩個屬性。其中第i個物品的重量為wt[i]，價值為val[i]，現在讓你用這個背包裝物品，最多能裝的價值是多少？
// 該問題其實是經典背包問題的變形，可以先對集合求和，得出sum,該問題就可以轉換為背包問題：
// 給一個可裝載重量為sum / 2的背包和N個物品，每個物品的重量為nums[i],現在讓你裝物品，是否存在一種裝法，能夠恰好將背包裝滿
// 1. 明確狀態和選擇
// 狀態就是背包容量和可選擇的物品
// 選擇就是裝進背包和不裝進背包
// 2. dp數組函數
// dp[i][j] = x表示，對于前i個物品，當前背包的容量為j時，若x為true，則說明可以恰好將背包裝滿，若x為false，則說明不能恰好將背包裝滿。
// 3. 狀態轉移邏輯
// 若放不進去，dp[i][j] = dp[i - 1][j]
// 若能夠放進去dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]
// 4. base case
// base case就是：
// (1)有物品但是容量為0,肯定能裝滿，此時即dp[……][0] = true
// (2)沒有物品但是有容量時，肯定裝不滿，此時即dp[0][……] = false
function canPartition(nums) {
let sums = 0;
nums.forEach(num => sums += num);
// 如果是奇數，不能被劃分，直接返回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]就是起結果,因為此時能找到和的一半，另一半也是和的一半
return dp[numsLen][sums / 2];
}零錢兌換II
給你一個整數數組 coins 表示不同面額的硬幣，另給一個整數 amount 表示總金額。
請你計算并返回可以湊成總金額的硬幣組合數。如果任何硬幣組合都無法湊出總金額，返回 0 。
假設每一種面額的硬幣有無限個。
題目數據保證結果符合 32 位帶符號整數。
示例 1：
輸入：amount = 5, coins = [1, 2, 5] 輸出：4 解釋：有四種方式可以湊成總金額： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
// 該問題可轉換為有一個背包，最大容量為amount，有一系列物品coins，每個物品的重量為coins[i]，每個物品的數量無限。請問有多少種方法，能夠把背包恰好裝滿？
// 與經典背包區別的是每個物品的數量是無限的，這也就是完全背包問題。
// 1. 狀態和選擇
// 狀態：背包的容量和可選擇的物品
// 選擇：放進背包和不放進背包
// 2. 定義dp
// dp[i][j]:若只使用前i個物品，當背包容量為j時，有dp[i][j]種方法可以裝滿背包。換句話說：若只使用coins中的前i個硬幣的面值，若想湊出金額j，有dp[i][j]中湊法
// 3. 狀態轉移邏輯
// 若不能放進去：dp[i][j] = dp[i - 1][j]
// 若能夠放進去：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - coins[i]]
// 4. base case
// (1)有硬幣，但是目標結果為0，即dp[0……n][0] = 1
// (2)沒有硬幣，即dp[0][0……n] = 0
function 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++) {
// 如果當前硬幣不能放進背包
if (j < coins[i - 1]) {
dp[i][j] = dp[i - 1][j];
} else {
// 能放進去，則結果就是放進去與不放進去的加和
// 為什么當放進去的時候為i，因為此時已經決定使用coins[i - 1]的值
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
}
}
}
// 目標結果就是[N, amount]
return dp[n][amount];
}
// 通過觀察發現dp[i][j]之和dp[i][……]和dp[i - 1][……]相關
// 則可進行狀態壓縮
function change1(amount, coins) {
// 定義dp
const dp = (new Array(amount + 1)).fill(0);
// base case
dp[0] = 1;
// 進行遍歷
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
有一堆石頭，用整數數組 stones 表示。其中 stones[i] 表示第 i 塊石頭的重量。
每一回合，從中選出任意兩塊石頭，然后將它們一起粉碎。假設石頭的重量分別為 x 和 y，且 x <= y。那么粉碎的可能結果如下：
如果 x == y，那么兩塊石頭都會被完全粉碎； 如果 x != y，那么重量為 x 的石頭將會完全粉碎，而重量為 y 的石頭新重量為 y-x。 最后，最多只會剩下一塊 石頭。返回此石頭 最小的可能重量 。如果沒有石頭剩下，就返回 0。
示例 1：
輸入：stones = [2,7,4,1,8,1] 輸出：1 解釋： 組合 2 和 4，得到 2，所以數組轉化為 [2,7,1,8,1]， 組合 7 和 8，得到 1，所以數組轉化為 [2,1,1,1]， 組合 2 和 1，得到 1，所以數組轉化為 [1,1,1]， 組合 1 和 1，得到 0，所以數組轉化為 [1]，這就是最優值。
// 該問題和分割等和子集問題（416）處理方式類似，就是背包問題
// 1. 狀態和選擇
// 狀態：背包和當前可選物品
// 選擇：是否裝進背包
// 2. dp數組含義
// dp[w][i]表示背包容量為w時，前i個物品，最多能夠裝的物品重量
// 3. 狀態轉移邏輯
// 不能裝進去：dp[w][i] = dp[w][i - 1]
// 能夠裝進去：dp[w][i] = Math.max(dp[w][i - 1], dp[w - stones[i]][i - 1] + stones[i])
// 4. base case
// 當i = 0時，dp[0……w][0] = 0
// 當w = 0時，dp[0][……] = 0
function 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 在初始化時已經完成
// 循環遍歷
for (let w = 1; w < dp.length; w++) {
for (let i = 1; i < dp[0].length; i++) {
// 判斷是否可以裝進去
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));目標和
給你一個整數數組 nums 和一個整數 target 。
向數組中的每個整數前添加 '+' 或 '-' ，然后串聯起所有整數，可以構造一個 表達式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串聯起來得到表達式 "+2-1" 。 返回可以通過上述方法構造的、運算結果等于 target 的不同 表達式 的數目。
示例 1：
輸入：nums = [1,1,1,1,1], target = 3 輸出：5 解釋：一共有 5 種方法讓最終目標和為 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
// 該方法可以用背包解決
// 如何轉換為01背包問題呢？
// 假設加法的總和為x，那么減法對應的總和就是sum - x
// 所以我們要求的就是x - (sum - x) = S
// x = (S + sum) / 2
// 此時問題就轉化為：裝滿容量為x背包，有幾種方法
// 1. 狀態和選擇
// 2. dp數組含義
// dp[i][w]：前i個物品、背包容量為w時，有幾種方式裝滿
// 3. 狀態轉移邏輯
// 裝不進去：dp[i][w] = dp[i - 1][w]
// 能裝進去：dp[i][w] = dp[i - 1][w - nums[i]] + dp[i - 1][w]
// 4. base case
// dp[0][0] = 1
function findTargetSumWays(nums, target) {
// 求和
const sum = nums.reduce((total, num) => total + num);
// weight必須大于0且為整數
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;
// 循環
for (let i = 1; i < dp.length; i++) {
for (let w = 0; w < dp[i].length; w++) {
// 不能裝進去
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];
}
// 用回溯算法實現一遍
function findTargetSumWays1(nums, target) {
let result = 0;
const backtrack = (index, sum) => {
// 結束條件
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));
