文章鏈接

1049. 最后一塊石頭的重量 II

解題關鍵：找到重量和盡量相等的兩堆

1. 確定dp數組以及下標的含義

• dp[j]表示容量（這里說容量更形象，其實就是重量）為j的背包，最多可以背最大重量為dp[j]。

1. 確定遞推公式

• 01背包的遞推公式為：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

• 本題則是：dp[j] =max(dp[j], dp[j - stones[i]] + stones[i])

1. dp數組初始化

2. 確定遍歷順序

public class Solution {public int LastStoneWeightII(int[] stones) {int[] dp=new int[15001];int sum=0;foreach(int stone in stones){sum+=stone;}int target=sum/2;for(int i=0;i<stones.Length;i++){for(int j=target;j>=stones[i];j--){dp[j]=Math.Max(dp[j],dp[j-stones[i]]+stones[i]);}}return sum-2*dp[target];}
}

494.目標和

加法集合left，減法集合right

left+right=sum

left-right=target

righ=sum-left

left-(sum-left)=target

left=(target+sum)/2

遞推公式：

二維DP數組遞推公式： dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

去掉維度i 之后，遞推公式：dp[j] = dp[j] + dp[j - nums[i]] ，即：dp[j] += dp[j - nums[i]]

public class Solution {public int FindTargetSumWays(int[] nums, int target) {int sum=0;foreach(int num in nums){sum+=num;}// 如果目標絕對值大于總和，無法組成if (Math.Abs(target) > sum) return 0;// 如果總和加目標值為奇數，無法整除2，無解if ((sum + target) % 2 == 1) return 0;// 計算背包容量，即子集P的和int bagSize = (sum + target) / 2;// dp[j]表示和為j的子集數量int[] dp = new int[bagSize + 1];// 和為0的子集只有一種情況：空集dp[0] = 1;for(int i=0;i<nums.Length;i++){for(int j = bagSize; j >= nums[i]; j--){dp[j] += dp[j - nums[i]];}}return dp[bagSize];}
}

474.一和零

dp[i][j]：裝滿i個0，j個1最大有dp[i][j]個物品

遞推公式：dp[i][j]=max(dp[i-x][j-y]+1,dp[i,j]

初始化：dp[0][0]=0

總結

• 純 0 - 1 背包 (opens new window)是求 給定背包容量 裝滿背包 的最大價值是多少。

• 416. 分割等和子集 (opens new window)是求 給定背包容量，能不能裝滿這個背包。

• 1049. 最后一塊石頭的重量 II (opens new window)是求 給定背包容量，盡可能裝，最多能裝多少

• 494. 目標和 (opens new window)是求 給定背包容量，裝滿背包有多少種方法。

• 本題是求 給定背包容量，裝滿背包最多有多少個物品。

public class Solution
{public int FindMaxForm(string[] strs, int m, int n){// 問題：從字符串數組中選出最多的字符串，使其包含的0不超過m個，1不超過n個// 這是一個二維01背包問題：每個字符串是一個物品，有兩個重量參數(0的數量和1的數量)// 背包容量限制為m(0的最大數量)和n(1的最大數量)// dp[i,j]表示使用i個0和j個1時能容納的最大字符串數量int[,] dp = new int[m + 1, n + 1];// 遍歷每個字符串(物品)foreach (string str in strs){// 統計當前字符串中0和1的數量int zero = 0, one = 0;foreach (char c in str){if (c == '0') zero++;else one++;}// 二維01背包的倒序遍歷，防止重復使用同一物品// 從大到小遍歷0的數量for (int i = m; i >= zero; i--){// 從大到小遍歷1的數量for (int j = n; j >= one; j--){// 狀態轉移方程：// 不選當前字符串：保持dp[i,j]不變// 選當前字符串：dp[i-zero, j-one] + 1(加1表示選了當前字符串)// 取兩種選擇的最大值dp[i, j] = Math.Max(dp[i, j], dp[i - zero, j - one] + 1);}}}// 返回使用不超過m個0和n個1時能容納的最大字符串數量return dp[m, n];}
}