P1048 [NOIP 2005 普及組] 采藥 題解復盤模塊動態(tài)規(guī)劃類型01背包目標在有限時間內(nèi)選擇若干草藥使總價值最大基本信息項目內(nèi)容題目編號、來源P1048 NOIP 2005 普及組訓練層級普及知識版塊01背包、一維DP、狀態(tài)轉(zhuǎn)移解題前?關鍵信號識別維度分析目標、約束、底層結構在規(guī)定時間 T 內(nèi)采摘草藥使價值最大。每株草藥只能采一次因此每個物品只有選和不選兩種狀態(tài)。底層結構為 01 背包。數(shù)據(jù)規(guī)模T≤1000M≤100可以使用 O(MT) 的動態(tài)規(guī)劃。候選算法和依據(jù)暴力枚舉每株草藥選不選復雜度 O(2^M)無法通過。使用動態(tài)規(guī)劃將問題轉(zhuǎn)化為 01 背包。復雜度預判時間復雜度O(M×T)空間復雜度O(T)解題后?外化復盤維度內(nèi)容狀態(tài)定義定義dp[j]表示在當前已經(jīng)考慮的草藥中使用時間不超過 j 時能夠獲得的最大價值。狀態(tài)轉(zhuǎn)移對于第 i 株草藥不選擇dp[j]選擇dp[j-t[i]]v[i]轉(zhuǎn)移方程dp[j]max(dp[j],dp[j-t[i]]v[i])遍歷順序01背包必須倒序遍歷容量for(jT;jt[i];j--)原因防止同一個物品被重復選擇。實現(xiàn)結構 / 核心思路1. 枚舉每一株草藥。2. 使用一維數(shù)組 dp 保存當前時間限制下的最大價值。3. 對時間倒序更新保證每株草藥只使用一次。錯因回溯容易錯誤地將循環(huán)寫成正序?qū)е乱粋€物品被重復使用變成完全背包。邊界和易錯點1. 01背包容量必須倒序。2. 答案為dp[T]。3. dp 初始化為 0 即可。下次看到什么信號我應該想到這個方法看到① 有容量限制② 每個物品只能選擇一次③ 求最大價值想到01背包容量倒序。AC完整代碼#includeiostream#includealgorithmusingnamespacestd;intmain(){intT,M;cinTM;intt[1005],v[1005];intdp[1005]{0};for(inti1;iM;i){cint[i]v[i];}for(inti1;iM;i){for(intjT;jt[i];j--){dp[j]max(dp[j],dp[j-t[i]]v[i]);}}coutdp[T];return0;}P1616 瘋狂的采藥 題解復盤模塊動態(tài)規(guī)劃類型完全背包目標在有限時間內(nèi)無限次選擇草藥使價值最大基本信息項目內(nèi)容題目編號、來源P1616 洛谷原創(chuàng)訓練層級普及知識版塊完全背包、一維DP、狀態(tài)轉(zhuǎn)移解題前?關鍵信號識別維度分析目標、約束、底層結構在規(guī)定時間內(nèi)獲得最大價值。每種草藥可以無限采摘因此同一個物品可以重復選擇。底層結構為完全背包。數(shù)據(jù)規(guī)模m≤10000t≤10^7且 m×t≤10^7。需要使用一維DP。候選算法和依據(jù)因為物品可以無限選擇所以不能使用01背包。使用完全背包模型。復雜度預判時間復雜度O(M×T)空間復雜度O(T)解題后?外化復盤維度內(nèi)容狀態(tài)定義定義dp[j]表示在時間不超過 j 的情況下可以獲得的最大價值。狀態(tài)轉(zhuǎn)移對于第 i 種草藥不選擇dp[j]選擇一次dp[j-a[i]]b[i]轉(zhuǎn)移方程dp[j]max(dp[j],dp[j-a[i]]b[i])遍歷順序完全背包需要正序遍歷容量for(ja[i];jt;j)原因允許當前物品更新后的狀態(tài)繼續(xù)參與轉(zhuǎn)移實現(xiàn)重復選擇。實現(xiàn)結構 / 核心思路1. 枚舉每種草藥。2. 使用一維 dp 保存時間限制下的最大價值。3. 容量正序更新使同一種草藥可以被多次使用。錯因回溯1. 容易將循環(huán)寫成倒序?qū)е峦耆嘲兂?1背包。2. 最大價值可能超過 int 范圍需要使用 long long。邊界和易錯點1. 完全背包容量必須正序。2. dp 數(shù)組使用 long long。3. 注意時間范圍 t 最大為 10^7。下次看到什么信號我應該想到這個方法看到① 有容量限制② 物品可以無限選擇③ 求最大價值想到完全背包容量正序。AC完整代碼#includeiostream#includealgorithmusingnamespacestd;inta[10005];intb[10005];longlongdp[10000005];intmain(){intt,m;cintm;for(inti1;im;i){cina[i]b[i];}for(inti1;im;i){for(intja[i];jt;j){dp[j]max(dp[j],dp[j-a[i]]b[i]);}}coutdp[t];return0;}