背包初步（0-1背包、完全背包）

當月光灑在我的臉上
我想我就快變了模樣
有一種叫做撕心裂肺的湯
喝了它有神奇的力量

動態規劃初步（完全背包）

0-1背包簡介

在「背包 dp」前，先來看如下的例題：

P2871 [USACO07DEC] Charm Bracelet S - 洛谷

有n個物品和一個容量為m的背包，每個物品有重量 w和價值 v兩種屬性，要求選若干物品放入背包使背包中物品的總價值最大且背包中物品的總重量不超過背包的容量。

在上述例題中，由于每個物體只有兩種可能的狀態（取與不取），對應二進制中的0和1，這類問題便被稱為「0-1 背包問題」。

dp狀態f(i,j)為在只能放前i個物品的情況下，容量為j的背包所能達到的最大總價值。

考慮轉移。假設當前已經處理好了前i-1個武平的所有狀態，那么對于第i個物品:

當其不放入背包時，背包的剩余容量不變，背包中物品的總價值也不變，故這種情況的最大價值為f(i-1,j)；
當其放入背包時，背包的剩余容量會減小v，背包中物品的總價值會增大w，故這種情況的最大價值為f(i-1,j-w)+v。

由此可以得出狀態轉移方程： $f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_i}+v_i)$

但是，這里如果直接采用二維數組對狀態進行記錄，會出現MLE。可以考慮改用滾動數組的形式來優化。

由于對f(i)有影響的只有f(i-1)，可以去掉第一維，直接用f(i)來表示處理到當前物品時背包容量為i的最大價值，得出以下方程： $fj=max?(fj,fj?wi+vi)f_j=\max\left(f_j,f_{j-w_i}+v_i\right)$

大部分背包問題的轉移方程都是在此基礎上推導出來的。

核心代碼就這個狀態轉移

for(int j=m;j>0;j--){if(w<=j)dp[j]=max(dp[j],dp[j-w]+d);
}

相關練習

P1048 [NOIP 2005 普及組] 采藥 - 洛谷

P1049 [NOIP 2001 普及組] 裝箱問題 - 洛谷

P1060 [NOIP 2006 普及組] 開心的金明 - 洛谷

278. 數字組合 - AcWing題庫

P1164 小A點菜 - 洛谷

完全背包

完全背包模型與0-1背包類似，與0-1背包的區別僅在于一個物品可以選取無限次，而非僅能選取一次。

我們可以借鑒0-1背包的思路，進行狀態定義：設f()i,j為只能選前i個物品時，容量為j的背包可以達到的最大價值。

雖然定義與 0-1 背包類似，但是其狀態轉移方程與0-1背包并不相同。

可以考慮一個樸素的做法：對于第i件物品，枚舉其選了多少個來轉移。這樣做的時間復雜度是O(n³)的。

狀態轉移方程如下：

$fi,j=max?k=0+∞(fi?1,j?k×wi+vi×k)f_{i,j}=\max_{k=0}^{+\infty}(f_{i-1,j-k\times w_i}+v_i\times k)$

做一個簡單的優化。可以發現，對于f(i,j)，只要通過f(i,j-w)轉移就可以了。因此狀態轉移方程為：

$f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i)$

與 0-1 背包相同，我們可以將第一維去掉來優化空間復雜度

$f_{j}=\max(f_j,f_{j-w_i}+v_i)$

完全背包在寫的時候根據題目目的的不同還要討論兩層for循環的前后順序

如果求組合數就是外層for循環遍歷物品，內層for遍歷背包。
如果求排列數就是外層for遍歷背包，內層for循環遍歷物品。

完全背包和 0-1 背包的區別就在于對時間大小枚舉的順序不同，0-1背包在內層循環時是倒序的，因為每個物品只能選一次，倒序選擇保證了第i個物品只會被放入背包一次；倒序循環滿足了0-1背包問題中物品唯一的要求；而完全背包沒有數量的限制所以可以正序枚舉；

檢查數組是否存在有效劃分（前綴劃分DP）

2369. 檢查數組是否存在有效劃分 - 力扣（LeetCode）

為了下面一道題能理解完全背包的劃分思想，我已先看了這一道題；仔細觀察發現居然是麻將！！

我們要在手牌中判斷能否湊成對子，刻子和順子；但是不能排序，所以必須要是子區間才可以；

一開始想的是用前兩天學的滑動窗口，但是無法實現，就看題目的提示開始dp；直接套用分析的模板開始分析！

DP五部曲：

狀態定義：

dp[i] 表示考慮數組的前 i 個元素（即 nums[0] 到 nums[i-1]）是否能被有效劃分（true/false）。
狀態轉移：

通過三種子數組劃分方式進行狀態轉移：
- 情況1：最后2個元素相等時，從 dp[i-2] 轉移
  dp[i] |= (nums[i-1] == nums[i-2]) && dp[i-2]
- 情況2：最后3個元素相等時，從 dp[i-3] 轉移
  dp[i] |= (i>=3 && nums[i-1]==nums[i-2] && nums[i-2]==nums[i-3]) && dp[i-3]
- 情況3：最后3個元素連續遞增（差值1）時，從 dp[i-3] 轉移
  dp[i] |= (i>=3 && nums[i-1]==nums[i-2]+1 && nums[i-2]==nums[i-3]+1) && dp[i-3]
狀態轉移方程
dp[i] = (最后2個相等且dp[i-2]) || (最后3個相等且dp[i-3]) || (最后3個連續遞增且dp[i-3])
初始化（邊界值）：
- dp[0] = true; // 空數組視為可劃分
- dp[1] = false; // 單個元素不可劃分
遍歷順序：
- 正序遍歷索引 i 從 2 到 n（含端點）
- dp[i] 依賴 dp[i-2] 和 dp[i-3]，需優先計算小索引
返回形式：返回 dp[n]，表示整個數組能否被有效劃分

分析完后，整體代碼就呼之欲出

class Solution {
public:bool validPartition(vector<int>& a) {if(a.size()<2)return 0;vector<bool> dp(a.size()+1,0);dp[0]=1;for(int i=2;i<=a.size();i++){bool f1=0,f2=0,f3=0;if(a[i-1]==a[i-2]){f1=dp[i-2];}if(i>2&&a[i-1]==a[i-2]&&a[i-1]==a[i-3]){f2=dp[i-3];}if(i>2&&a[i-1]==a[i-2]+1&&a[i-1]==a[i-3]+2){f3=dp[i-3];}dp[i]=f1||f2||f3;}return dp[a.size()];}
};

從這題開始，下面的才是正宗的完全背包

單詞拆分(求排列數)

139. 單詞拆分 - 力扣（LeetCode）

鋪墊那么久，終于開始引入正題；題目要求用給定的字符串數組中的元素拼出s，不限數量；不要求全部用上，但是拼的時候不能有重疊部分；我們需要判斷能否拼出來；里面單詞就是物品，字符串s就是背包，單詞能否組成字符串s，就是問物品能不能把背包裝滿。也就是我們所學的完全背包；

DP五部曲：

狀態定義:

dp[i] : 字符串長度為i的話，dp[i]為true，表示可以拆分為一個或多個在字典中出現的單詞。
狀態轉移:確定遞推公式
- 如果確定dp[j] 是true，且 [j, i] 這個區間的子串出現在字典里，那么dp[i]一定是true（j < i ）。
狀態轉移方程

if ([j, i] 這個區間的子串出現在字典里 && dp[j]是true) dp[i] = true
初始化(邊界值):

從遞推公式中可以看出，dp[i] 的狀態依靠 dp[j]是否為true，那么dp[0]就是遞推的根基，dp[0]一定為true，否則遞推下去后面都都是false了。
遍歷順序:

題目中說是拆分為一個或多個在字典中出現的單詞，所以這是完全背包。還要討論兩層for循環的前后順序。這道題需要剛好拼滿，不能重疊不能遺漏；所以是求排列數，外層for遍歷背包，內層for循環遍歷物品。（其實就是為了方便截取字符串去比較）
返回形式: dp[s.size()]就是最終結果。

class Solution {
public:bool wordBreak(string s, vector<string>& a) {vector<bool> dp(s.size()+1,0);dp[0]=1;for(int i=1;i<=s.size();i++){bool ff=0;for(int j=0;j<a.size();j++){if(a[j].size()<=i){string t=s.substr(i-a[j].size(),a[j].size());if(t==a[j])ff|=dp[i-t.size()];}}dp[i]=ff;}return dp[s.size()];}
};

瘋狂的采藥（求組合數）

P1616 瘋狂的采藥 - 洛谷

采草藥，每種藥沒有限制，盡可能總價值越多越好；在這道題目中容易被草藥的價值所迷惑；仔細分析總時間是背包，采摘草藥所需的時間是物品，我們需要在時間里面分配采摘的情況使得草要的總價值最大；所以與上一題不同，這題需要物品在外，背包在內（求組合數）

DP五部曲：最大化價值

狀態定義：

dp[j] 表示在時間限制 j 內能獲得的最大價值：
- j 的取值范圍：0 到 t（總可用時間）
- 目標：dp[t] 即時間限制 t 下的最大價值
狀態轉移:

采用完全背包策略（每種藥材可采無限次）：dp[j] = max(dp[j], dp[j - 采藥時間] + 藥材價值)

轉移說明：
- 不采當前藥材：保留原值 dp[j]
- 采當前藥材：從 j - 采藥時間 轉移，加上新價值
- 轉移方程：
  dp[j] = max(dp[j], dp[j - a[i].fi] + a[i].se)
初始化:

dp[0] = 0; // 0 時間內無法采藥，價值為 0
dp[j] = 0; // 所有初始值設為 0（通過全局數組初始化實現）
遍歷順序:

外層循環：遍歷藥材 i 從 1 到 m（物品維度）

內層循環：順序枚舉時間j從a[i].fi到t（容積維度）

從低到高正序遍歷（完全背包特性）起點為當前藥材所需時間 a[i].fi
返回形式:輸出 dp[t] 即時間上限 t 時的最大價值

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
const int N=1e7+7;
int dp[N];
pii a[N];
void slove(){int t,m;cin>>t>>m;for(int i=1;i<=m;i++)cin>>a[i].fi>>a[i].se;for(int i=1;i<=m;i++){for(int j=a[i].fi;j<=t;j++)dp[j]=max(dp[j],dp[j-a[i].fi]+a[i].se);}cout<<dp[t];
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;//cin>>_;while(_--)slove();return 0;
}

自然數拆分

279. 自然數拆分 - AcWing題庫

趁熱打鐵，再來練一道；一樣的思路一樣的套路；這題的兩種循環效果是一樣的，不同順序視為相同（屬于相同的劃分方案）

DP五部曲：整數劃分問題（方案數統計）

狀態定義

dp[j] 表示整數 j 可以被劃分的方案數（模 2147483648），包括：
- 使用1到j的整數進行劃分
- 允許重復使用相同的數
狀態轉移：

轉移方程：dp[j] = (dp[j] + dp[j-i]) % M
- 含義：對于每個整數i，當前整數j的劃分方案數等于：
  
  不使用 i 的方案數（dp[j]）加上使用至少一個 i 的方案數（dp[j-i]）
初始化（邊界值）

dp[0] = 1; // 空劃分：用0個數表示0的方案數為1
dp[i] = 0; // 其他值初始化為0（通過vector初始化）
遍歷順序
- 外層循環：枚舉使用的數 i 從 1 到 4003（覆蓋可能的n值）
- 內層循環：枚舉整數 j 從 i 到 4003（從小到大遍歷）
- 順序要求：正序枚舉背包容量（完全背包模型）
返回形式
- 輸入目標整數 n
- 返回(dp[n] - 1) mod M其中：(減1表示排除只包含自身的情況)
  
  dp[n] 包含劃分成單個整數的方案
- 當 dp[n] 為0時，輸出 2147483647（即 M-1）

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
const int N=4004;
const int M=2147483648;
int dp[N];
void slove(){int n;cin>>n;dp[0]=1;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){dp[j]=(dp[j]+dp[j-i])%M;}}int an=dp[n];if(an==0)an=M-1;elsean--;cout<<an<<endl;
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;//cin>>_;while(_--)slove();return 0;
}