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