01背包問題的空間優化與邊界處題目解析

01背包問題是經典的動態規劃問題，旨在選擇若干物品裝入背包，使得總價值最大且不超過背包容量。每個物品只能選或不選（0或1），不可分割。

選和不選是01背包問題最大的特征

例題

01背包

題目鏈接：

01背包

要點：

老師代碼：

#include <iostream>
#include <string.h>using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N][N];int main()
{// 讀?數據cin >> n >> V;for(int i = 1; i <= n; i++)cin >> v[i] >> w[i];// 解決第?問for(int i = 1; i <= n; i++)for(int j = 0; j <= V; j++) // 修改遍歷順序{dp[i][j] = dp[i - 1][j];if(j >= v[i])dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);}cout << dp[n][V] << endl;// 解決第?問memset(dp, 0, sizeof dp);for(int j = 1; j <= V; j++) dp[0][j] = -1;for(int i = 1; i <= n; i++)for(int j = 0; j <= V; j++) // 修改遍歷順序{dp[i][j] = dp[i - 1][j];if(j >= v[i] && dp[i - 1][j - v[i]] != -1)dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);}cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;return 0;
}

空間優化：

#include <iostream>
#include <string.h>
using namespace std;const int N = 1010;
int n, V, v[N], w[N];
int dp[N];int main()
{// 讀?數據cin >> n >> V;for(int i = 1; i <= n; i++)cin >> v[i] >> w[i];// 解決第?問for(int i = 1; i <= n; i++)for(int j = V; j >= v[i]; j--) // 修改遍歷順序dp[j] = max(dp[j], dp[j - v[i]] + w[i]);cout << dp[V] << endl;// 解決第?問memset(dp, 0, sizeof dp);for(int j = 1; j <= V; j++) dp[j] = -1;for(int i = 1; i <= n; i++)for(int j = V; j >= v[i]; j--)if(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;
}

老師思路：

第一問：

狀態表?：dp[i][j] 表?：從前 i 個物品中挑選，總體積「不超過」 j ，所有的選法中，能挑選出來的最?價值
狀態轉移?程：線性 dp 狀態轉移?程分析?式，?般都是根據「最后?步」的狀況，來分情況討論：
- i. 不選第 i 個物品：相當于就是去前 i - 1 個物品中挑選，并且總體積不超過 j 。此時 dp[i][j] = dp[i - 1][j] ；
- ii. 選擇第 i 個物品：那么我就只能去前 i - 1 個物品中，挑選總體積不超過 j - v[i] 的物品。此時 dp[i][j] = dp[i - 1][j - v[i]] + w[i] 。但是這種狀態不?定存在，因此需要特判?下。
- 綜上，狀態轉移?程為： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) 。
初始化：我們多加??，?便我們的初始化，此時僅需將第??初始化為 0 即可。因為什么也不選，也能滿?體積不?于 j 的情況，此時的價值為 0 。
填表順序：根據「狀態轉移?程」，我們僅需「從上往下」填表即可。
返回值：根據「狀態表?」，返回 dp[n][V] 。

第二問

第?問僅需微調?下 dp 過程的五步即可。因為有可能湊不? j 體積的物品，因此我們把不合法的狀態設置為 -1 。

狀態表?：dp[i][j] 表?：從前 i 個物品中挑選，總體積「正好」等于 j ，所有的選法中，能挑選出來的最?價值。
狀態轉移?程：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) 。但是在使? dp[i - 1][j - v[i]] 的時候，不僅要判斷 j >= v[i] ，?要判斷 dp[i- 1][j - v[i]] 表?的情況是否存在，也就是 dp[i - 1][j - v[i]] != -1
初始化：我們多加??，?便我們的初始化：i. 第?個格?為 0 ，因為正好能湊?體積為 0 的背包； ii. 但是第??后?的格?都是 -1 ，因為沒有物品，?法滿?體積?于 0 的情況
填表順序：根據「狀態轉移?程」，我們僅需「從上往下」填表即可。
返回值：由于最后可能湊不成體積為 V 的情況，因此返回之前需要「特判」?下。

我的代碼：

#include <iostream>
#include <vector>
using namespace std;int main()
{int n, v;cin >> n >> v;vector<int> sz(n + 1);vector<int> val(n + 1);for(int i = 1; i <= n; i++) cin >> sz[i] >> val[i];//狀態表示vector<vector<int>> dp1(n + 1, vector<int>(v + 1));auto dp2 = dp1;//初始化for(int j = 1; j <= v; j++) dp2[0][j] = -1;//使空位置的物品價值等于j是不存在的，而不是物品價值為0，所以填入-1//填表for(int i = 1; i <= n; i++){for(int j = 0; j <= v; j++){dp1[i][j] = dp1[i - 1][j];if(sz[i] <= j) dp1[i][j] = max(dp1[i][j], dp1[i - 1][j - sz[i]] + val[i]);dp2[i][j] = dp2[i - 1][j];if(sz[i] <= j && dp2[i - 1][j - sz[i]] != -1) dp2[i][j] = max(dp2[i][j], dp2[i - 1][j - sz[i]] + val[i]);}}cout << dp1[n][v] << endl;cout << (dp2[n][v] == -1 ? 0 : dp2[n][v]) << endl;return 0;
}

我的思路：

老師教的

對于第一問：

狀態表示：dp[i][j]表示 i 位置之前的物品能夠裝入背包體積不大于 j 的最大價值
狀態轉移方程：
- 如果不選 i 位置的物品就要從 i - 1位置的物品中選擇能夠裝入背包體積不大于 j 的最大價值
  
  dp[i][j] = dp[i - 1][j];
- 如果選 i 位置的物品就要判斷能不能選，如果不能就選擇前面的方案，如果能選，則我們選上當前位置的物品val[i]之后還要從 i - 1 位置的物品中選擇體積不超過j - sz[i] 的最大價值，最后吧這一種方案與前面一種方案取最大值即可
  
  if(sz[i] <= j) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - sz[i]] + val[i]);

對于第二問：

狀態表示：dp[i][j]表示位置之前的物品能夠裝入背包體積剛好等于 j 的最大價值
狀態轉移方程：
- 如果不選 i 位置的物品，我們就要從 i - 1 位置中選出裝入背包體積等于 j 的最大價值
  
  dp[i][j] = dp[i - 1][j]這和之前的狀態轉移方程是一樣的，因為狀態表示變了
- 如果選 i 位置的物品，我們仍然要判斷能不能選，此時還有一種情況，就是存不存在可以選 i 位置物品的情況，因為如果要使體積剛好等于 j 這種情況可能是不存在的，所以要多加一個判斷條件
  
  if(sz[i] <= j && dp2[i - 1][j - sz[i]] != -1) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - sz[i]] + val[i])

注意：dp2[i - 1][j - sz[i]] != -1用-1判斷是因為我們需要與0的意義區分開，0表示dp[i][j]表示位置之前的物品能夠裝入背包體積剛好等于 j 的最大價值為0，而不是沒有這種情況，只是價值為0而已

我的筆記:

還是要注意數組下標的映射關系，這個比較容易出錯，不管是在輸入數據、初始化、填表的時候
背包問題的思想
對于空間優化的建議：
- 不要深究空間優化之后狀態表示以及狀態轉移方程的實際含義
- 空間優化重點是處理后面的填表中用不到的數據
- 注意填表方式可能不同，原因就是不能覆蓋還需要的數據

分割等和子集

題目鏈接：

分割等和子集

要點：

問題核心：判斷數組是否能被分割成兩個和相等的子集。關鍵在于找到子集和為總和的一半。
數學條件：若總和為奇數，直接返回false；若最大元素超過總和一半，也直接返回false。
動態規劃定義：dp[i][j]表示前i個元素是否能選出和為j的子集。

老師代碼：

class Solution
{
public:bool canPartition(vector<int>& nums){int n = nums.size(), sum = 0;for(auto x : nums) sum += x;if(sum % 2) return false; // 如果不能平分，直接返回 falseint aim = sum / 2; // 定義?下?標值vector<vector<bool>> dp(n + 1, vector<bool>(aim + 1)); // 建表for(int i = 0; i <= n; i++) dp[i][0] = true; // 初始化for(int i = 1; i <= n; i++) // 填表for(int j = 1; j <= aim; j++){dp[i][j] = dp[i - 1][j];if(j >= nums[i - 1])dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];}// 返回結果return dp[n][aim];}
}

空間優化：

class Solution
{
public:bool canPartition(vector<int>& nums){int n = nums.size(), sum = 0;for(auto x : nums) sum += x;if(sum % 2) return false; // 如果不能平分，直接返回 falseint aim = sum / 2; // 定義?下?標值vector<bool> dp(aim + 1); // 建表dp[0] = true; // 初始化for(int i = 1; i <= n; i++) // 填表for(int j = aim; j >= nums[i - 1]; j--) // ?定要注意修改遍歷順序dp[j] = dp[j] || dp[j - nums[i - 1]];// 返回結果return dp[aim];}
};

老師思路：

先將問題轉化成我們「熟悉」的題型。

如果數組能夠被分成兩個相同元素之和相同的?集，那么原數組必須有下??個性質：

i. 所有元素之和應該是?個偶數；
ii. 數組中最?的元素應該?于所有元素總和的?半；
iii. 挑選?些數，這些數的總和應該等于數組總和的?半。

根據前兩個性質，我們可以提前判斷數組能夠被劃分。根據最后?個性質，我們發現問題就轉化成了「01 背包」的模型：

i. 數組中的元素只能選擇?次；
ii. 每個元素?臨被選擇或者不被選擇的處境；
iii. 選出來的元素總和要等于所有元素總和的?半。

其中，數組內的元素就是物品，總和就是背包。那么我們就可以?背包模型的分析?式，來處理這道題。

請?家注意，「不要背」狀態轉移?程，因為題型變化之后，狀態轉移?程就會跟著變化。我們要記住的是分析問題的模式。?這種分析問題的模式來解決問題

狀態表?：dp[i][j] 表?在前 i 個元素中選擇，所有的選法中，能否湊成總和為 j 這個數
狀態轉移?程：?規矩，根據「最后?個位置」的元素，結合題?的要求，分情況討論：
- i. 不選擇 nums[i] ：那么我們是否能夠湊成總和為 j ，就要看在前 i - 1 個元素中選，能否湊成總和為 j 。根據狀態表?，此時 dp[i][j] = dp[i - 1][j]；
- ii. 選擇 nums[i] ：這種情況下是有前提條件的，此時的 nums[i] 應該是?于等于 j 。因為如果這個元素都?要湊成的總和?，選擇它就沒有意義呀。那么我們是否能夠湊成總和為 j ，就要看在前 i - 1 個元素中選，能否湊成總和為 j - nums[i] 。根據狀態表?，此時 dp[i][j] = dp[i - 1][j - nums[i]] 。
綜上所述，兩種情況下只要有?種能夠湊成總和為 j ，那么這個狀態就是 true 。因此，狀態轉移?程為：

dp[i][j] = dp[i - 1][j] if(nums[i - 1] <= j) dp[i][j] = dp[i][j] || dp[i - 1][j -nums[i]]
初始化：由于需要?到上??的數據，因此我們可以先把第??初始化。第??表?不選擇任何元素，要湊成?標和 j 。只有當?標和為 0 的時候才能做到，因此第??僅需初始化第?個元素 dp[0][0] = true
填表順序：根據「狀態轉移?程」，我們需要「從上往下」填寫每??，每??的順序是「?所謂的」。
返回值：根據「狀態表?」，返回 dp[n][aim] 的值。其中 n 表?數組的??， aim 表?要湊的?標和。
空間優化：所有的「背包問題」，都可以進?空間上的優化。對于 01背包類型的，我們的優化策略是： i. 刪掉第?維；ii. 修改第?層循環的遍歷順序即可。

我的代碼：

class Solution {
public:bool canPartition(vector<int>& nums) {int m = nums.size();int sum = 0;for(int i = 0; i < m; i++)sum += nums[i];if(sum % 2) return false;//如果數組和為一個奇數，則他一定不能分成兩個相等的整數int k = sum / 2;vector<vector<bool>> dp(m + 1, vector<bool>(k + 1));//初始化for(int i = 0; i <= m; i++) dp[i][0] = true;//填表for(int i = 1; i <= m; i++){for(int j = 0; j <= k; j++){dp[i][j] = dp[i - 1][j];if(j - nums[i - 1] >= 0) dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];}}return dp[m][k];}
};

空間優化：

class Solution {
public:bool canPartition(vector<int>& nums) {int m = nums.size();int sum = 0;for(int i = 0; i < m; i++)sum += nums[i];if(sum % 2) return false;int k = sum / 2;vector<bool> dp(k + 1);//初始化dp[0] = true;//填表for(int i = 1; i <= m; i++){for(int j = k; j >= 0; j--){if(j - nums[i - 1] >= 0) dp[j] = dp[j] || dp[j - nums[i - 1]];}}return dp[k];}
};

我的思路：

將問題轉化為“是否存在子集和為sum/2”，轉化為01背包問題。
初始化dp[0][0] = true（空集和為0），其他dp[0][j] = false（j > 0時無法用空集湊出）。

我的筆記:

如何將這一個問題轉化為01背包問題
數組下標映射關系
為什么要多開一行一列的dp空間？因為當我們不選也就是子集為空，以及和為0的情況是有研究價值的，也就是會出現這種情況的

目標和

題目鏈接：

目標和

要點：

問題轉化：設正數和為a，負數和為b，則a - b = target且a + b = sum，推導得a = (sum + target) / 2。
合法性判斷：若(sum + target)為奇數或target絕對值超過sum，直接返回0

老師代碼：

class Solution
{
public:int findTargetSumWays(vector<int>& nums, int target){int sum = 0;for(auto x : nums) sum += x;int aim = (sum + target) / 2;// 處理?下邊界條件if(aim < 0 || (sum + target) % 2) return 0;int n = nums.size();vector<vector<int>> dp(n + 1, vector<int>(aim + 1)); // 建表dp[0][0] = 1; // 初始化for(int i = 1; i <= n; i++) // 填表for(int j = 0; j <= aim; 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][aim];}
}

老師思路：

本題可以直接?「暴搜」的?法解決。但是稍微?數學知識分析?下，就能轉化成我們常?的「背包模型」的問題。

設我們最終選取的結果中，前?加 + 號的數字之和為 a ，前?加 - 號的數字之和為 b ，整個數組的總和為 sum ，于是我們有：

a + b = sum

a - b = target

上?兩個式?消去 b 之后，可以得到 a = (sum + target) / 2 也就是說，我們僅需在 nums 數組中選擇?些數，將它們湊成和為 (sum + target) / 2 即可。問題就變成了 416. 分割等和?集這道題。我們可以?相同的分析模式，來處理這道題

狀態表?：dp[i][j] 表?：在前 i 個數中選，總和正好等于 j ，?共有多少種選法。
狀態轉移?程：?規矩，根據「最后?個位置」的元素，結合題?的要求，我們有「選擇」最后?個元素或者「不選擇」最后?個元素兩種策略：
- i. 不選 nums[i] ：那么我們湊成總和 j 的總?案，就要看在前 i - 1 個元素中選，湊成總和為 j 的?案數。根據狀態表?，此時 dp[i][j] = dp[i - 1][j] ；
- ii. 選擇 nums[i] ：這種情況下是有前提條件的，此時的 nums[i] 應該是?于等于 j 。因為如果這個元素都?要湊成的總和?，選擇它就沒有意義呀。那么我們能夠湊成總和為 j 的?案數，就要看在前 i - 1 個元素中選，能否湊成總和為 j - nums[i] 。根據狀態表?，此時 dp[i][j] = dp[i - 1][j - nums[i]]
- 綜上所述，兩種情況如果存在的話，應該要累加在?起。因此，狀態轉移?程為：dp[i][j] = dp[i - 1][j] if(nums[i - 1] <= j) dp[i][j] = dp[i][j] += dp[i - 1][j - nums[i- 1]]
初始化：由于需要?到「上??」的數據，因此我們可以先把第??初始化。第??表?不選擇任何元素，要湊成?標和 j 。只有當?標和為 0 的時候才能做到，因此第??僅需初始化第?個元素 dp[0][0] = 1
填表順序：根據「狀態轉移?程」，我們需要「從上往下」填寫每??，每??的順序是「?所謂的」。
返回值：根據「狀態表?」，返回 dp[n][aim] 的值。其中 n 表?數組的??， aim 表?要湊的?標和
空間優化：所有的「背包問題」，都可以進?空間上的優化。對于 01背包類型的，我們的優化策略是：
- i. 刪掉第?維；
- ii. 修改第?層循環的遍歷順序即可

我的代碼：

class Solution 
{
public:int findTargetSumWays(vector<int>& nums, int target) {int m = nums.size();int sum = 0;for(auto& n : nums) sum += n;if((sum + target) % 2) return 0;//如果是奇數，則一定不存在一種情況使int k = (sum + target) / 2;//如果k的值小于0，這種情況下是找不到的，因為題目給了nums中的數是大于0的if(k < 0) return 0;vector<vector<int>> dp(m + 1, vector<int>(k + 1));//初始化dp[0][0] = 1;//填表for(int i = 1; i <= m; i++){for(int j = 0; j <= k; j++)//這里要從0開始，因為按照題目要求，nums[i]可能為0{ dp[i][j] = dp[i - 1][j];if(j - nums[i - 1] >= 0) dp[i][j] = dp[i][j] + dp[i - 1][j - nums[i - 1]];}}return dp[m][k];}
};

空間優化：

class Solution 
{
public:int findTargetSumWays(vector<int>& nums, int target) {int m = nums.size();int sum = 0;for(auto& n : nums) sum += n;if((sum + target) % 2) return 0;//如果是奇數，則一定不存在一種情況使int k = (sum + target) / 2;if(k < 0) return 0;vector<int> dp(k + 1);//初始化dp[0] = 1;//填表for(int i = 1; i <= m; i++){for(int j = k; j - nums[i - 1] >= 0; j--){dp[j] += dp[j - nums[i - 1]];}}return dp[k];}
};

我的思路：

使用動態規劃統計組成和為a的方案數，狀態轉移方程為：
dp[j] += dp[j - nums[i]]（若j >= nums[i]）。
初始化dp[0] = 1，表示空集和為0的方案數為1。

我的筆記:

注意邊界條件，包括sum + target的值不能為奇數（因為k涉及除法可能存在除不盡的問題），以及k的值不能小于0（nums[i]都是大于0的數）
要看清題目要求
原始數組與dp表的下標映射關系

最后一塊石頭的重量II

題目鏈接：

最后一塊石頭的重量II

要點：

問題轉化：將石頭粉碎過程轉化為對數組元素賦予正負號，使得兩部分的差值最小。最終結果等價于求數組分割成兩個子集的最小差值。
數學推導：設總和為sum，理想分割為兩子集和接近sum/2，差值最小為sum - 2*max_subset_sum。
狀態轉移優化：用01背包求不超過sum/2的最大子集和，直接計算最終差值。

老師代碼：

class Solution
{
public:int lastStoneWeightII(vector<int>& stones){// 1. 準備?作int sum = 0;for(auto x : stones) sum += x;int n = stones.size(), m = sum / 2;// 2. dpvector<vector<int>> dp(n + 1, vector<int>(m + 1));for(int i = 1; i <= n; i++)for(int j = 0; j <= m; j++){dp[i][j] = dp[i - 1][j];if(j >= stones[i - 1])dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] +stones[i - 1]);}// 3. 返回結果return sum - 2 * dp[n][m];}
}

老師思路：

先將問題「轉化」成我們熟悉的題型。? 任意兩塊?頭在?起粉碎，重量相同的部分會被丟掉，重量有差異的部分會被留下來。那就相當于在原始的數據的前?，加上「加號」或者「減號」，是最終的結果最?即可。也就是說把原始的?頭分成兩部分，兩部分的和越接近越好。? ?因為當所有元素的和固定時，分成的兩部分越接近數組「總和的?半」，兩者的差越?。因此問題就變成了：在數組中選擇?些數，讓這些數的和盡量接近 sum / 2 ，如果把數看成物品，每個數的值看成體積和價值，問題就變成了「01 背包問題」

我的代碼：

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int m = stones.size();int sum = 0;for(auto& s : stones) sum += s;int k = sum / 2;vector<vector<int>> dp(m + 1, vector<int>(k + 1));//填表for(int i = 1; i <= m; i++){for(int j = 0; j <= k; j++){dp[i][j] = dp[i - 1][j];if(j - stones[i - 1] >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);}}return sum - 2 * dp[m][k];}
};

我的思路：
1.兩個石頭相撞，結果要么為x-y，要么為y-x
2.無論你怎么兩兩相碰，永遠有的數字前為正號，有的為負號,因此你總可以把最終式化為一堆和減去另外一堆數字和
3.因此我們要找的是這個集合的兩個子集之和的最小差
4.要想子集之和差最小，則兩者應該盡量接近或者相等
5.這個時候我們就可以把sum/2作為背包容量，使用01背包來解題了

我的筆記:

若總和為奇數，sum/2向下取整不影響結果，因為差值只關心兩部分的和差距。
空間優化時，內層循環需逆序遍歷，防止覆蓋未使用的上一狀態

解決01背包問題的注意事項

C++語法細節

數組下標設計：
- 從1開始存儲物品信息，避免處理i-1的邊界問題（如nums[i-1]對應第i個物品）。
- 二維dp表可優化為一維數組，但需逆序更新防止覆蓋。
數據類型選擇：
- 若結果可能較大（如目標和方案數），使用long long避免溢出。
- vector初始化時，默認值需根據問題設定（如-1表示非法狀態，0或1表示初始方案數）。
空間優化實現：
- 一維dp數組更新時，內層循環必須逆序（從大到小），保證每個物品只選一次。
- 初始化需單獨處理dp[0]，如dp[0] = 1（目標和問題）或dp[0] = 0（最大價值問題）。

算法思路核心

狀態定義：
- 明確dp[i][j]的含義，例如“前i個物品中選出體積不超過j的最大價值”或“組成和為j的方案數”。
狀態轉移方程：
- 分“選”與“不選”兩種情況討論，注意合法性判斷（如體積不足時不能選）。
- 累加或取最大值需根據問題目標調整。
邊界條件處理：
- 初始化時，dp[0][0]通常有特殊含義（如空集和為0），其他位置根據問題設定初始值。
- 處理負值或非法狀態（如dp[j] = -1表示無法湊出體積j）。
問題轉化技巧：
- 將復雜問題轉化為背包模型，如“分割等和子集”轉化為求子集和等于sum/2。
- 利用數學公式簡化問題，如“目標和”中推導出a = (sum + target)/2。