在OJ上做P1734“最大約數(shù)和”這道題時(shí)很多人的第一反應(yīng)是約數(shù)和跟背包有什么關(guān)系難道要先把1到S的約數(shù)和全算出來(lái)再暴力湊組合可等你把題意真正翻譯完就會(huì)發(fā)現(xiàn)這是一道特別典型的動(dòng)態(tài)規(guī)劃01背包題所有背包要素都在只是把“體積”換成了數(shù)字本身把“價(jià)值”換成了約數(shù)和。用這道題來(lái)理解01背包比背十遍模板都有用因?yàn)樗颇闳ハ肭宄總€(gè)物品到底能不能重復(fù)選數(shù)組為什么要倒著更新?tīng)顟B(tài)里存的到底是“恰好”還是“不超過(guò)”這篇文章我會(huì)從題意開(kāi)始拆把狀態(tài)設(shè)計(jì)、約數(shù)和預(yù)處理、一維滾動(dòng)數(shù)組的完整實(shí)現(xiàn)、常見(jiàn)踩坑點(diǎn)全部過(guò)一遍。適合剛學(xué)動(dòng)態(tài)規(guī)劃不久、想找一道題鞏固背包模型的人也適合準(zhǔn)備競(jìng)賽但一直被各種背包變體繞暈的同學(xué)。1. 拆開(kāi)P1734的題面約數(shù)和只是“價(jià)值”的包裝1.1 題目到底在問(wèn)什么輸入的S是一個(gè)正整數(shù)要求你從1、2、3、……、S這些正整數(shù)里選若干個(gè)數(shù)出來(lái)。有兩個(gè)約束第一選出來(lái)的數(shù)必須“互不相同”也就是說(shuō)每個(gè)數(shù)字最多只能被選一次第二這些選出來(lái)的數(shù)的總和不能超過(guò)S。最后每個(gè)被選中的數(shù)都會(huì)貢獻(xiàn)自己的“約數(shù)和”作為得分目標(biāo)是讓總得分最大。舉個(gè)具體例子S4數(shù)字1的約數(shù)和是1數(shù)字2的約數(shù)和是123數(shù)字3的約數(shù)和是134數(shù)字4的約數(shù)和是1247。如果只選4總和是4剛好不超過(guò)S得分7選1和3總和也是4得分145選1和2總和3得分134。所以S4時(shí)最優(yōu)方案就是單選4答案是7。再看S5這個(gè)例子特別能說(shuō)明問(wèn)題。數(shù)字5的約數(shù)和是156如果只看單個(gè)數(shù)字6已經(jīng)不小了。但選1和4總和5得分178比單選5還大。也就是說(shuō)不能貪心不能看到某個(gè)數(shù)“單個(gè)價(jià)值高”就直接選它必須用背包把所有組合的價(jià)值都算出來(lái)。1.2 “不同正整數(shù)”決定了這是01背包題目里明確要求“若干個(gè)不同的正整數(shù)”這一點(diǎn)非常關(guān)鍵。每個(gè)數(shù)字只能出現(xiàn)一次對(duì)應(yīng)01背包中每個(gè)物品最多取一次。如果題目改成“可以重復(fù)選取同一個(gè)數(shù)字”那就是完全背包狀態(tài)轉(zhuǎn)移時(shí)容量方向的處理方式完全不同答案也會(huì)差很多。我記得剛帶某位同學(xué)做這道題時(shí)他把“每個(gè)數(shù)只能選一次”理解成了“每種數(shù)值可以重復(fù)”結(jié)果S4的時(shí)候他算出答案是10因?yàn)樗x了兩次2約數(shù)和336再加1的1總得分7不對(duì)他實(shí)際上是用了完全背包模板得到了錯(cuò)誤結(jié)果。后來(lái)我讓他把選擇方案列出來(lái)他才發(fā)現(xiàn)同一個(gè)數(shù)字被用了多次這不滿(mǎn)足題意。所以看到“不同”兩個(gè)字第一反應(yīng)就應(yīng)該是01背包。還有一點(diǎn)容易被忽略題目要求“和不超過(guò)S”不是“恰好等于S”。也就是說(shuō)背包不需要裝滿(mǎn)最后dp[S]里存的就是所有容量不超過(guò)S的情況中的最大值。這個(gè)區(qū)別決定初始化方式因?yàn)樵试S不裝dp數(shù)組全為0就能表示合法狀態(tài)如果題目要求恰好裝滿(mǎn)初始化時(shí)要讓dp[0]0其他dp[j]設(shè)為負(fù)無(wú)窮。1.3 約數(shù)和到底包不包括它自己“約數(shù)和”這三個(gè)字在不同題目里可能有細(xì)微差別。有人會(huì)下意識(shí)認(rèn)為“約數(shù)”不包括自身其實(shí)不是。P1734這里的約數(shù)和指的是一個(gè)數(shù)所有正約數(shù)之和其中包含1和這個(gè)數(shù)本身。比如4的正約數(shù)是1、2、4所以約數(shù)和是7。如果題目想讓你求“真約數(shù)和”一般會(huì)明確說(shuō)“不包括自身”或者“除自身以外”。比賽時(shí)遇到含糊表述看樣例能猜出來(lái)P1734的樣例和常見(jiàn)題解都按包含自身處理。預(yù)處理約數(shù)和時(shí)這個(gè)“包含自身”的性質(zhì)很重要因?yàn)樗屛锲返膬r(jià)值可能大于物品本身的體積。比如2的重量是2價(jià)值是3價(jià)值比重量還大所以選2往往很劃算。但即使如此也不代表我們應(yīng)該貪心選所有“價(jià)值大于重量”的數(shù)因?yàn)槿萘坑邢捱x了它可能擠掉其他組合。這就是背包問(wèn)題需要?jiǎng)討B(tài)規(guī)劃的根本原因局部最優(yōu)拼不出全局最優(yōu)。2. 把P1734翻譯成01背包狀態(tài)、轉(zhuǎn)移、滾動(dòng)數(shù)組2.1 背包三要素在題目里的對(duì)應(yīng)關(guān)系標(biāo)準(zhǔn)01背包問(wèn)題有三個(gè)關(guān)鍵概念物品、容量、價(jià)值。P1734里這三樣?xùn)|西一開(kāi)始有點(diǎn)隱蔽但對(duì)應(yīng)關(guān)系非常規(guī)整背包概念P1734中的對(duì)應(yīng)物品數(shù)量數(shù)字1到S共S個(gè)物品第i個(gè)物品的體積數(shù)字i本身的大小第i個(gè)物品的價(jià)值數(shù)字i的約數(shù)和val[i]背包容量所選數(shù)字的總和上限S每個(gè)物品的選取次數(shù)最多選1次這樣一對(duì)照問(wèn)題就清晰了我們有一個(gè)容量為S的背包有S個(gè)“數(shù)字物品”每個(gè)數(shù)字的體積就是它的編號(hào)價(jià)值是它的約數(shù)和問(wèn)最大能裝多少價(jià)值。很多同學(xué)會(huì)困惑“體積怎么等于編號(hào)”這是這類(lèi)題目的特殊設(shè)計(jì)但并不影響背包模型。你只需要把每個(gè)i當(dāng)做一個(gè)獨(dú)立的物品它的體積是一個(gè)整數(shù)i價(jià)值是處理好的val[i]就行了。甚至如果題目改成“從2到S里選”也只需要把物品范圍換一下。2.2 二維狀態(tài)定義與轉(zhuǎn)移方程如果不做空間壓縮先寫(xiě)二維版本是最容易理解的。設(shè)dp[i][j]表示考慮前i個(gè)數(shù)字也就是數(shù)字1到i從它們中選若干個(gè)選出的數(shù)字總和不超過(guò)j時(shí)能得到的最大約數(shù)和。那么對(duì)于數(shù)字i有兩種決策不選它dp[i][j] dp[i-1][j]選它但前提是j idp[i][j] max(dp[i][j], dp[i-1][j-i] val[i])為什么用dp[i-1][j-i]而不是dp[i][j-i]因?yàn)檫@里要求數(shù)字i只能選一次所以必須從“完全沒(méi)有考慮過(guò)數(shù)字i”的上一層狀態(tài)轉(zhuǎn)移過(guò)來(lái)。如果寫(xiě)成dp[i][j-i]那表示當(dāng)前數(shù)字i已經(jīng)被選擇過(guò)再?gòu)哪莻€(gè)狀態(tài)繼續(xù)選就會(huì)變成可以重復(fù)選擇同一數(shù)字模型就錯(cuò)了。最終答案是dp[S][S]。二維數(shù)組的大小是(S1) x (S1)本題S很小直接開(kāi)二維也能過(guò)。但為了把01背包的理解再往前推一步我建議你直接學(xué)會(huì)一維滾動(dòng)數(shù)組因?yàn)榻^大多數(shù)背包題的優(yōu)化套路最后都指向它。2.3 一維數(shù)組為什么必須倒序遍歷觀察二維轉(zhuǎn)移dp[i][]只依賴(lài)dp[i-1][]所以可以用一維dp反復(fù)覆蓋。壓縮后狀態(tài)變成dp[j]表示當(dāng)前已經(jīng)處理到某個(gè)數(shù)字時(shí)容量為j的背包能獲得的最大價(jià)值。偽代碼是這個(gè)樣子for i 1 to S: for j S down to i: dp[j] max(dp[j], dp[j-i] val[i])內(nèi)層循環(huán)必須從大到小也就是“倒序遍歷容量”。原因很簡(jiǎn)單我們希望在計(jì)算dp[j]時(shí)用到的dp[j-i]還是上一層的舊值而不是已經(jīng)被當(dāng)前數(shù)字i更新過(guò)的新值。如果正序從i到S掃描那么在枚舉當(dāng)前數(shù)字i時(shí)dp[j-i]可能已經(jīng)被本輪更新過(guò)里面可能已經(jīng)包含了一次數(shù)字i再用它轉(zhuǎn)移就相當(dāng)于又把數(shù)字i放進(jìn)去一次等于允許數(shù)字i被重復(fù)選取。用一個(gè)最小的例子說(shuō)明。S2數(shù)字1的約數(shù)和是1。倒序計(jì)算j2時(shí)dp[2]max(dp[2], dp[1]1)此時(shí)dp[1]還是0所以dp[2]1j1時(shí)dp[1]max(dp[1], dp[0]1)得到1。最終dp[2]1正確因?yàn)槿萘?只放一個(gè)數(shù)字1價(jià)值就是1。如果正序j1時(shí)dp[1]1j2時(shí)dp[2]max(0, dp[1]1)2相當(dāng)于放入了兩個(gè)數(shù)字1錯(cuò)誤。倒序的本質(zhì)是保證每個(gè)物品只被拿一次。生活里類(lèi)比一下一個(gè)背包的檢查清單要從后往前打勾才不會(huì)被“當(dāng)前物品已經(jīng)放進(jìn)背包”的情況誤導(dǎo)。2.4 初始值為什么全為0這里要區(qū)分“不超過(guò)S”和“恰好裝滿(mǎn)S”兩種問(wèn)題的初始化差異。P1734要求的是不超過(guò)S那么空背包就是一個(gè)合法方案價(jià)值為0。所以dp數(shù)組全部初始化為0沒(méi)問(wèn)題dp[0]0順理成章。如果某道題要求“恰好用完容量S”那么只有容量0是合法起點(diǎn)其他容量初始應(yīng)該為負(fù)無(wú)窮表示“無(wú)法恰好裝滿(mǎn)”。因?yàn)椤安怀^(guò)”比“恰好”少了限制P1734直接用全0初始化就好這也是背包類(lèi)題目里最省心的一種情況。3. 完整實(shí)現(xiàn)約數(shù)和預(yù)處理 一維01背包3.1 約數(shù)和預(yù)處理方式對(duì)比在套背包之前必須先把每個(gè)數(shù)字的約數(shù)和算出來(lái)。數(shù)據(jù)范圍很小但依然有兩種常用做法建議都掌握。方法一試除法對(duì)每個(gè)i枚舉到sqrt(i)如果j是i的約數(shù)那么i/j也是i的約數(shù)。累加時(shí)注意平方數(shù)的去重。for (int i 1; i S; i) { for (int j 1; j * j i; j) { if (i % j 0) { val[i] j; if (j * j ! i) { val[i] i / j; } } } }復(fù)雜度是O(S sqrt S)。S1000級(jí)別時(shí)完全沒(méi)問(wèn)題。這個(gè)方法思路直白適合現(xiàn)場(chǎng)很快寫(xiě)出來(lái)。方法二倍數(shù)篩法用倍數(shù)關(guān)系的角度把每個(gè)可能的約數(shù)d累加到它的所有倍數(shù)x上。for (int d 1; d S; d) { for (int x d; x S; x d) { val[x] d; } }比如d1會(huì)加到所有數(shù)上d2會(huì)加到2、4、6……上這樣就保證每個(gè)x的val里包含了它所有約數(shù)d之和。這個(gè)寫(xiě)法更短復(fù)雜度O(S log S)在S稍大一些時(shí)也能跑。兩種方法放在一起我更推薦倍數(shù)篩因?yàn)椴蝗菀茁┘s數(shù)也不需要判斷平方根去重。3.2 核心AC代碼下面給出一份完整的C代碼可直接運(yùn)行#include bits/stdc.h using namespace std; const int MAXN 1005; int val[MAXN]; int dp[MAXN]; int main() { int S; cin S; // 預(yù)處理1到S的約數(shù)和 for (int d 1; d S; d) { for (int x d; x S; x d) { val[x] d; } } // 01背包一維倒序 for (int i 1; i S; i) { for (int j S; j i; j--) { dp[j] max(dp[j], dp[j - i] val[i]); } } cout dp[S] endl; return 0; }這里有三個(gè)細(xì)節(jié)要提醒。第一外層循環(huán)i一定要從1跑到S不要只跑到S-1因?yàn)閱为?dú)選擇數(shù)字S本身是一個(gè)合法且可能最優(yōu)的方案。第二內(nèi)層循環(huán)從S到i利用了ji這個(gè)條件不需要在循環(huán)體內(nèi)再單獨(dú)判斷效率也高。第三dp只需要開(kāi)S1大小因?yàn)槿萘可舷蘧褪荢。如果打算用Python思路完全一樣S int(input()) val [0] * (S 1) for d in range(1, S 1): for x in range(d, S 1, d): val[x] d dp [0] * (S 1) for i in range(1, S 1): for j in range(S, i - 1, -1): dp[j] max(dp[j], dp[j - i] val[i]) print(dp[S])3.3 手工模擬一遍S4把轉(zhuǎn)移過(guò)程看穿很多人寫(xiě)背包題喜歡直接套板子一旦出錯(cuò)就不知道從哪查。我強(qiáng)烈建議你手工模擬一輪小數(shù)據(jù)比如S4。初始dpdp[0]0, dp[1]0, dp[2]0, dp[3]0, dp[4]0。處理數(shù)字1val[1]1j4: dp[4]max(0, dp[3]1)1j3: dp[3]1j2: dp[2]1j1: dp[1]1此時(shí)dp[0,1,1,1,1]表示只用數(shù)字1時(shí)容量至少為1都能得到價(jià)值1。處理數(shù)字2val[2]3j4: dp[4]max(1, dp[2]3)134表示選數(shù)字2和1組合容量3但當(dāng)前容量4同樣得到4j3: dp[3]max(1, dp[1]3)134j2: dp[2]max(1, dp[0]3)3現(xiàn)在dp[0,1,3,4,4]。處理數(shù)字3val[3]4j4: dp[4]max(4, dp[1]4)145j3: dp[3]max(4, dp[0]4)4dp[0,1,3,4,5]。容量4下選1和3得5確實(shí)比選1和2得4更好。處理數(shù)字4val[4]7j4: dp[4]max(5, dp[0]7)7最后dp[4]7和前面手算一致。這個(gè)過(guò)程能看到每個(gè)數(shù)字只被考慮一次而且容量方向從高到低所以即使數(shù)字4的價(jià)值很高它也只能和dp[0]組合不能和已經(jīng)加入過(guò)數(shù)字4的狀態(tài)再組合。3.4 二維轉(zhuǎn)一維是“省內(nèi)存”但不是“省思考”二維寫(xiě)法更容易驗(yàn)證轉(zhuǎn)移邏輯一維寫(xiě)法代碼更短。但一維寫(xiě)法真正考驗(yàn)?zāi)愕牟皇谴a而是你是否理解“倒序保證不重復(fù)”和“覆蓋順序的意義”。如果遇到一道新題不敢確定建議第一遍先寫(xiě)二維跑通之后再壓縮成一維。壓縮之后如果結(jié)果不一致優(yōu)先檢查內(nèi)層循環(huán)是不是倒序。在實(shí)際競(jìng)賽中空間限制緊張時(shí)一維幾乎是必須的。P1734雖然二維也能過(guò)但養(yǎng)成一維習(xí)慣沒(méi)有壞處。尤其以后遇到二維背包、多重背包你會(huì)發(fā)現(xiàn)“滾動(dòng)數(shù)組倒序”是貫穿始終的基本功。4. 實(shí)戰(zhàn)排查P1734和01背包路上的常見(jiàn)坑4.1 內(nèi)層循環(huán)正序把01背包寫(xiě)成了完全背包這是最經(jīng)典的錯(cuò)誤沒(méi)有之一。癥狀是代碼邏輯看起來(lái)沒(méi)問(wèn)題但輸出偏大而且數(shù)字越小越明顯。比如S2時(shí)預(yù)期答案是1卻輸出2那就是數(shù)字1被用了兩次。排查方法很簡(jiǎn)單把內(nèi)層循環(huán)的j改成從S到i倒序再重新跑樣例。如果答案恢復(fù)正常就說(shuō)明你踩了這個(gè)坑。很多模板題解都強(qiáng)調(diào)“倒序”但真正自己寫(xiě)的時(shí)候手一滑就寫(xiě)成了for(int ji; jS; j)。我建議在代碼注釋里直接寫(xiě)明“倒序防重復(fù)”。4.2 約數(shù)和預(yù)處理漏掉平方根去重用試除法算約數(shù)和時(shí)最常見(jiàn)的bug是對(duì)于完全平方數(shù)像16j4是它的約數(shù)i/j4也是它的約數(shù)但它們是同一個(gè)數(shù)。如果不加if(j*j ! i)17的約數(shù)和就會(huì)被算成1162844多了一次4最終價(jià)值偏大。正確寫(xiě)法是j加入后如果i/j不等于j才再加入i/j。或者干脆用倍數(shù)篩從根源上避免這種問(wèn)題。倍數(shù)篩的缺點(diǎn)是稍微有點(diǎn)反直覺(jué)但寫(xiě)熟了以后非常穩(wěn)。4.3 物品范圍少枚舉了一個(gè)S很多人寫(xiě)循環(huán)時(shí)習(xí)慣寫(xiě)for(int i1; iS; i)潛意識(shí)里認(rèn)為“背包容量都是S放進(jìn)一個(gè)體積等于S的物品就沒(méi)法再裝其他東西了是不是沒(méi)必要”但這不是“沒(méi)必要”而是可能“最優(yōu)”。S4時(shí)單獨(dú)放數(shù)字4價(jià)值7大于任何組合如果不枚舉i4答案會(huì)變成5。還有一點(diǎn)即使體積等于容量的物品價(jià)值不高你也要把它放進(jìn)物品列表。因?yàn)楸嘲鼏?wèn)題不要求裝滿(mǎn)單獨(dú)放一個(gè)體積等于容量的物品可能不是最優(yōu)但也有可能是是否最優(yōu)應(yīng)該交給dp來(lái)算而不是在枚舉范圍上手動(dòng)排除。4.4 初始化時(shí)把dp開(kāi)成“恰好裝滿(mǎn)”的負(fù)無(wú)窮有些同學(xué)做上一道“恰好裝滿(mǎn)”題時(shí)用了負(fù)無(wú)窮初始化到P1734沒(méi)改回來(lái)就會(huì)導(dǎo)致dp[S]從負(fù)無(wú)窮開(kāi)始狀態(tài)轉(zhuǎn)移結(jié)果可能少一個(gè)“什么都不選”的0分支。不過(guò)因?yàn)樽罱K答案一般會(huì)通過(guò)選數(shù)字得到正值這個(gè)問(wèn)題未必會(huì)讓答案變錯(cuò)但思路不干凈。記住一句話不超過(guò)容量dp全0恰好裝滿(mǎn)dp[0]0其余負(fù)無(wú)窮。4.5 多組輸入或多次運(yùn)行數(shù)組沒(méi)清空有些題干會(huì)隱藏多組數(shù)據(jù)或者你自己對(duì)拍時(shí)循環(huán)多次運(yùn)行。val和dp是全局?jǐn)?shù)組上一次運(yùn)行留下的臟數(shù)據(jù)會(huì)讓第二次結(jié)果異常。如果要用多組數(shù)據(jù)每次處理前memset(val, 0, sizeof(val))和memset(dp, 0, sizeof(dp))。用vector定義的話直接重新構(gòu)造或fill更方便。4.6 用小數(shù)據(jù)暴力枚舉驗(yàn)證DP當(dāng)你懷疑DP寫(xiě)錯(cuò)了最好的辦法不是反復(fù)盯代碼而是寫(xiě)一個(gè)暴力枚舉做對(duì)拍。對(duì)小數(shù)據(jù)S不超過(guò)10可以枚舉所有子集int brute(int S) { int ans 0; for (int mask 0; mask (1 S); mask) { int sum 0, score 0; for (int i 1; i S; i) { if (mask (1 (i - 1))) { sum i; score val[i]; } } if (sum S) ans max(ans, score); } return ans; }然后隨機(jī)生成S分別跑brute和dp比較結(jié)果。對(duì)拍是排查動(dòng)態(tài)規(guī)劃錯(cuò)誤的好習(xí)慣遇到“不知道錯(cuò)在哪”的時(shí)候就用小數(shù)據(jù)暴力兜底。S再小一點(diǎn)手動(dòng)枚舉也行。5. 從P1734里提煉出“一眼看穿01背包”的能力5.1 識(shí)別01背包的三個(gè)特征做過(guò)P1734之后再回頭看你會(huì)發(fā)現(xiàn)它的“馬甲”并不厚。所有01背包變體都具備這幾個(gè)共同點(diǎn)有一組元素每個(gè)元素只能使用一次有一個(gè)總量限制比如容量、體積、時(shí)間、預(yù)算要讓某個(gè)目標(biāo)值最大化或最小化。只要你從題目里讀出“每個(gè)物品最多選一次”和“總量不能超過(guò)X”就基本可以往01背包方向想。接下來(lái)要做的不是急著套模板而是回答三個(gè)問(wèn)題物品是什么每個(gè)物品的重量是多少每個(gè)物品的價(jià)值是多少以P1734為例物品是數(shù)字1到S重量是數(shù)字本身價(jià)值是約數(shù)和。把這三個(gè)問(wèn)題寫(xiě)在草稿紙上代碼自己就出來(lái)了。5.2 為什么不能靠貪心解決有人問(wèn)P1734里大多數(shù)數(shù)字的約數(shù)和都大于數(shù)字本身那我優(yōu)先選“性?xún)r(jià)比高”的行不行不行。背包問(wèn)題里體積和價(jià)值是獨(dú)立的你可能為了一個(gè)高價(jià)值物品占掉大量容量結(jié)果失去了組合出更高總價(jià)值的可能性。S5時(shí)單選4得7單選5得6但14得8就是一個(gè)反例。貪心適合的情況是物品可以分割比如分?jǐn)?shù)背包但01背包的物品不可分割并且每個(gè)只能選一次必須枚舉所有容量下的最優(yōu)狀態(tài)。這也是動(dòng)態(tài)規(guī)劃在這個(gè)問(wèn)題上不可替代的原因。5.3 常見(jiàn)01背包變體一覽以后做題可以自己歸類(lèi)普通背包體積w[i]價(jià)值v[i]容量V子集和問(wèn)題每個(gè)數(shù)重量等于值價(jià)值等于1或者直接判斷可行性數(shù)字組合問(wèn)題像P1734一樣重量就是數(shù)字本身價(jià)值是題目額外定義的函數(shù)最少物品湊容量容量固定每個(gè)物品重量固定求裝滿(mǎn)所需物品數(shù)的最小值其實(shí)價(jià)值可以等價(jià)為1的01背包。識(shí)別出變體后核心代碼只需要微調(diào)重量換一下、價(jià)值換一下、目標(biāo)是max還是min、初始化是0還是負(fù)無(wú)窮。把這幾件事想清楚比刷一百道同類(lèi)題還有用。5.4 如果題目要求輸出選擇方案有的擴(kuò)展題不光要最大值還要輸出選了哪些數(shù)字。二維做法比較直接轉(zhuǎn)移時(shí)用一個(gè)choose[i][j]布爾數(shù)組記錄dp[i][j]這個(gè)狀態(tài)是不是通過(guò)選擇數(shù)字i得到的。最后從dp[S][S]倒著回溯。一維做法也可以另開(kāi)一個(gè)last[j]表示達(dá)到dp[j]時(shí)最后一次放入的數(shù)字然后從S往前追int last[1005]; for (int i 1; i S; i) { for (int j S; j i; j--) { if (dp[j - i] val[i] dp[j]) { dp[j] dp[j - i] val[i]; last[j] i; } } }回溯時(shí)注意當(dāng)前容量j對(duì)應(yīng)的last[j]就是最后一個(gè)被放入的數(shù)字輸出它之后要把容量變成j-last[j]繼續(xù)看下一個(gè)last。這種記錄方式在競(jìng)賽里很實(shí)用但初學(xué)階段可以先不管把最優(yōu)值搞清楚再擴(kuò)展。5.5 練熟后你會(huì)有什么變化熟練之后再做P1734這種題你會(huì)本能地寫(xiě)出一套固定分析流程先看能不能重復(fù)再看容量上限然后找價(jià)值和體積。這種“建模能力”才是動(dòng)態(tài)規(guī)劃的核心競(jìng)爭(zhēng)力。模板只是最后幾步的代碼落地前期的分析才決定你能不能做對(duì)。我自己帶人做題時(shí)最欣慰的是看到對(duì)方不再問(wèn)“這題為什么用背包”而是能反過(guò)來(lái)分析“這個(gè)題如果改成每個(gè)數(shù)能用無(wú)限次內(nèi)層循環(huán)應(yīng)該怎么改”。能提出這個(gè)問(wèn)題說(shuō)明他是真的理解01背包了。最后再分享一個(gè)我用到現(xiàn)在的調(diào)試習(xí)慣看到任何背包題先別急著交手動(dòng)跑一個(gè)S4或S5的例子把dp數(shù)組每輪變化寫(xiě)出來(lái)確認(rèn)每一步都符合預(yù)期再提交。這個(gè)方法雖然笨但能幫你躲過(guò)至少一半的寫(xiě)法錯(cuò)誤。P1734是一道特別適合練習(xí)這個(gè)習(xí)慣的入門(mén)題把它吃透后面遇到再花哨的背包變體你也能一眼看穿。