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