[模版]01背包

1. 第一問: 背包不一定能裝滿

(1) 狀態表示

dp[i][[j]: 從前 i 個物品中挑選, 總體積不超過 j, 所有選法中, 能挑選出來的最大價值.

(2) 狀態轉移方程

根據最后一步的狀況, 分情況討論:

1. 不選 i 物品
   此時就是在前 i-1 個物品中挑選, 總體積不超過 j, 所有選法中, 能挑選出來的最大價值.

dp[i][j] = dp[i-1][j]

2. 選 i 物品
   選了 i 物品, 說明最后要加上 w[i], 此時就是在前 i-1 個物品中挑選, 總體積不超過 j - v[i], 所有選法中, 能挑選出來的最大價值.

dp[i][j] = dp[i-1][ j - v[i] ] + w[i]

注:j-v[i]可能不存在, 所以 j-v[i] >= 0
比如, j = 1, 但是 v[i] = 4 了, 此時 j-v[i] 為 負數了, 就是不存在的.

綜上, 狀態轉移方程為:

dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])

(3) 初始化

根據題意可知, 下標是從 1 開始的, 所以 dp表 會多一行多一列.
橫坐標代表物品數, 縱坐標代表體積.
第0行表示: 從前0個物品中挑選, 總體積不超過 j 的最大價值, 就是為0.
第0列表示: 從前 i 個物品中挑選, 總體積不超過 0 的最大價值, 物品都是有體積的, 這種情況也不存在, 也是為0.

所以可以不用特別的初始化, 默認為0即可.

(4) 填表順序

從上往下

(5) 返回值

根據狀態表示可知, 題目最終要返回的是, 從前 n 個物品中挑選, 總體積不超過 v 的最大價值.
即返回: dp[n][v].

2. 第二問: 背包恰好裝滿

與第一問的討論思路和過程是一模一樣, 狀態轉移方程也一樣, 只有以下幾點有細微的變化:

(1) 狀態表示
dp[i][[j]: 從前 i 個物品中挑選, 總體積恰好等于 j, 所有選法中, 能挑選出來的最大價值.

(2) 判斷狀態方程是否存在
在求每一個狀態時, 從前 i-1 個物品中選,可能會選不出體積恰好等于 j 的物品.
此時可以做一個約定: dp[i][j] = -1時, 表示沒有這種情況.
其實在第一種情況 不選 i 物品時, 是可以不用特判 dp[i-1][j] != -1的. 因為第一種情況不選 i 物品是一定存在的, 如果 dp[i-1][j] = -1, 那么 dp[i][j] = -1, 這是合理的.
但是第二種情況 選 i 物品時一定要特判 dp[i-1][j-v[i]] != -1. 因為第二種情況多加了一個 w[i], 如果 dp[i-1][j-v[i]] 等于 -1, 再加上 w[i], 就會影響最終結果了.

(3) 初始化
第一個格子為0 , 因為正好能湊齊體積為0 的背包, 但是第一行后面的格子都是 -1 , 因為沒有物品, 無法滿足體積大于 0 的情況.

(4) 返回值
最后有可能湊不出體積恰好為 V 的,所以返回之前要特判一下.

代碼實現如下:

#include <iostream>
#include <cstring>
using namespace std;const int N = 1010;
int n, V;
int v[N], w[N];
int dp[1010][1010];int main()
{cin >> n >> V;for(int i = 1; i <= n; i++) //下標從1開始cin >> v[i] >> w[i];//解決第一問for(int i = 1; i <= n; i++){for(int j = 1; j <= V; j++){dp[i][j] = dp[i-1][j];if(j - v[i] >= 0)dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);}}cout << dp[n][V] << endl;//解決第二問memset(dp, 0, sizeof(dp));for(int i = 1; i <= V; i++)dp[0][i] = -1;for(int i = 1; i <= n; i++){for(int j = 1; j <= V; j++){dp[i][j] = dp[i-1][j];// 注意要特判if(j - v[i] >= 0 && dp[i-1][j-v[i]] != -1)dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);}}cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;return 0;
}

3. 空間優化

1.利用滾動數組做空間上的優化
2.直接在原始的代碼上修改即可
步驟:

1.把二維dp表中的 i (所有橫坐標)去掉改成一維(不是改成一層循環,還是需要兩層循環,只是把dp表中的 i 去掉).
2.修改 j 的遍歷順序成從右往左.

修改后的代碼如下:

#include <iostream>
#include <cstring>
using namespace std;const int N = 1010;
int n, V;
int v[N], w[N];
int dp[1010];int main()
{cin >> n >> V;for(int i = 1; i <= n; i++) //下標從1開始cin >> v[i] >> w[i];//解決第一問for(int i = 1; i <= n; i++){for(int j = V; j >= 0; j--){dp[j] = dp[j];if(j - v[i] >= 0)dp[j] = max(dp[j], dp[j-v[i]] + w[i]);}}cout << dp[V] << endl;//解決第二問memset(dp, 0, sizeof(dp));for(int i = 1; i <= V; i++)dp[i] = -1;for(int i = 1; i <= n; i++){for(int j = V; j >= 0; j--){dp[j] = dp[j];// 注意要特判if(j - v[i] >= 0 && dp[j-v[i]] != -1)dp[j] = max(dp[j], dp[j-v[i]] + w[i]);}}cout << (dp[V] == -1 ? 0 : dp[V]) << endl;return 0;
}

416.分割等和子集

1. 狀態表示

dp[i][j]:從前 i 個數中選,和是否恰好等于 j ,是為true, 不是為false.

2. 狀態轉移方程

和01背包問題一樣, 根據第 i 個位置選或不選,分兩種情況討論:
(1) 不選第 i 個數: dp[i][j] = dp[i-1][j]
(2) 選第 i 個數: dp[i][j] = dp[i-1][j-nums[i]]
只要這兩種選法中有一個能湊成就是符合題意的, 所以可得:
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
注意: j - nums[i] >= 0.

3. 初始化

為了防止填表時出現越界問題,一般還是多開一行多開一列.
(0, 0) 位置, 從前 0 個數中選,和是否恰好等于 0, 成立, 所以是 true, 第一行的其他位置則為 false.
第一列, 從前 i 個數中選,和是否恰好等于 0, 成立, 所以第一列初始化為 true.

4. 填表順序

從上往下.

5. 返回值

本題可以轉化為: 在數組中選一些數, 讓這些數的和等于 sum / 2.(其中sum是整個數組的和).
所以最終返回: dp[n][sum / 2] 即可.

代碼實現如下:

class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size();int sum = 0;for(auto x : nums) sum += x;//當和為奇數時,不能等和分if(sum % 2 == 1) return false;vector<vector<bool>>dp(n+1, vector<bool>(sum+1));for(int j = 1; j <= sum; j++) dp[0][j] = false;for(int i = 0; i <= n; i++) dp[i][0] = true;for(int i = 1; i <= n; i++){for(int j = 1; j <= sum; j++){dp[i][j] = dp[i-1][j];if(j - nums[i-1] >= 0)dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];}}return dp[n][sum/2];}
};

空間優化后的代碼如下:

class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size();int sum = 0;for(auto x : nums) sum += x;if(sum % 2 == 1) return false;vector<bool>dp(vector<bool>(sum+1));for(int j = 1; j <= sum; j++) dp[j] = false;for(int i = 0; i <= n; i++) dp[0] = true;for(int i = 1; i <= n; i++){for(int j = sum; j >= 1; j--){dp[j] = dp[j];if(j - nums[i-1] >= 0)dp[j] = dp[j] || dp[j-nums[i-1]];}}return dp[sum/2];}
};

494. 目標和

我們先對這道題進行分析:
在添加完±號后會有正數和負數,我們把所有正數和記為a,所有負數和的絕對值記為b,總和記為sum.
根據題意可知: a-b=target, a+b=sum,可得 a = (sum+target)/2

所以原題可轉換為:在數組中選一些數，讓這些數字的和等于a，一共有多少種選法.
這就是一個01背包問題, 下面的分析過程和上一題 [416.分割等和子串] 基本一樣.

1. 狀態表示

dp[i][j]:從前 i 個數中選，使得總和為 j ，一共有多少種選法.

2. 狀態轉移方程

根據i位置的狀態，有兩種情況：
1.i 位置不選，dp[i][j] = dp[i-1][j]
2.i 位置選，dp[i][j] = dp[i-1][j-nums[i]]
注意: j >= nums[i].
綜上，兩種選法的總數:
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]

3. 初始化

依舊是多加一行多加一列.
第一行:數組里沒有元素，要湊成和為0,和為1… 都湊不出, 所以填 0, 但是 dp[0][0] = 1.
第一列:除了第一個位置，其余位置是可以不用特別初始化的.
因為本題的數字有可能是0,第一列表示的是從前 i 個數字中，總和為0的選法,那就會有很多種情況了。
而我們初始化的目的就是避免填表時越界訪問，而選第 i 個位置時，是用第二種情況,這種情況我們有前提條件 j >= nums[i]，當 j = 0 時, 要使用那個方程就要滿足 nums[i] = 0, 此時 dp[i][j] = dp[i-1][0], 這使得這種情況填表時只會使用表中的上一個位置，而不是越界訪問。

4. 填表順序

從上往下

5. 返回值

根據我們上面的分析可知, 最終返回: dp[n][a] 即可.

代碼實現如下:

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int n = nums.size();int sum = 0;for(auto x : nums) sum += x;int a = (sum + target) / 2;if(a < 0 || (sum + target) % 2 == 1) return 0;vector<vector<int>> dp(n+1, vector<int>(a+1));dp[0][0] = 1;for(int i = 1; i <= n; i++){for(int j = 0; j <= a; j++){dp[i][j] = dp[i-1][j];if(j >= nums[i-1])dp[i][j] += dp[i-1][j-nums[i-1]];}}return dp[n][a];}
};

空間優化后的代碼如下:

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int n = nums.size();int sum = 0;for(auto x : nums) sum += x;int a = (sum + target) / 2;if(a < 0 || (sum + target) % 2 == 1) return 0;vector<int> dp(vector<int>(a+1));dp[0] = 1;for(int i = 1; i <= n; i++){for(int j = a; j >= 1; j--){dp[j] = dp[j];if(j >= nums[i-1])dp[j] += dp[j-nums[i-1]];}}return dp[a];}
};

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

我們先來分析題目:
挑選兩個石頭粉碎，其實就是在任意兩個石頭前添加±號
分析思路同"目標和"一題，全部正數和記為a,負數和絕對值記為b. 要求的就是|a-b|的最小值。
而我們又知道全部數的總和sum, 即a+b=sum.
求|a-b|的最小值可以說成: 把一個數sum拆成兩個數，求這兩個數的差的最小值.
而只有當這兩個數越接近sum/2時，差就越小
綜上分析，本題可轉換為:
在數組中選擇一些數，讓這些數的和盡可能接近sum/2("這些數的和"就是上面的a或b).

本質就是一個01背包問題:
物品 - 數
每個物品的價值 - nums[i]
每個物品體積 - nums[i]
背包體積 - sum/2.
選一些數放進背包中，在不超過背包體積的情況下，里面的最大和是多少.

1. 狀態表示

dp[i][j]:從前i個數中選，總和不超過j,此時的最大和.

2. 狀態轉移方程

根據i位置的狀態，有兩種情況：
1.i 位置不選，dp[i][j] = dp[i-1][j]
2.i 位置選，dp[i][j] = dp[i-1][j-nums[i]] + nums[i]
注意: j >= nums[i].
綜上: dp[i][j] = max(dp[i-1][j] , dp[i-1][j-nums[i]])

3. 初始化

多一行多一列
第一行:背包中沒有石頭，無法湊成總和為0,1,2,3… 初始化為0即可
第一列:同 [目標和] 一題.

4. 填表順序

從上往下

5. 返回值

dp[n][sum/2] 就是上面分析中的 a，則 b = sum-dp[n][sum/2], 所以最小值為 a - b = sum - 2 * dp[n][sum/2].

代碼實現如下:

class Solution 
{
public:int lastStoneWeightII(vector<int>& stones) {int n = stones.size(), sum = 0;for(auto x : stones) sum += x;vector<vector<int>> dp(n+1, vector<int>(sum / 2 + 1));for(int i = 1; i <= n; i++){for(int j = 0; j <= sum / 2; j++){dp[i][j] = dp[i-1][j];if(j >= stones[i-1])dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i-1]] + stones[i-1]);}}// dp[n][sum/2]就是上面分析中的a，則b=sum-dp[n][sum/2]// 所以最小值為a-b=sum - 2 * dp[n][sum/2]return sum - 2 * dp[n][sum/2];}
};

空間優化后的代碼:

class Solution 
{
public:int lastStoneWeightII(vector<int>& stones) {int n = stones.size(), sum = 0;for(auto x : stones) sum += x;vector<int> dp(vector<int>(sum / 2 + 1));for(int i = 1; i <= n; i++){for(int j = sum / 2; j >= 1; j--){dp[j] = dp[j];if(j >= stones[i-1])dp[j] = max(dp[j], dp[j-stones[i-1]] + stones[i-1]);}}// dp[n][sum/2]就是上面分析中的a，則b=sum-dp[n][sum/2]// 所以最小值為a - b = sum - 2 * dp[sum/2]return sum - 2 * dp[sum/2];}
};