絕對經(jīng)典背包九講完整版

1、背包問題九講vl.O目錄第一講01背包問題第二講完全背包問題第三講多重背包問題第四講混合三種背包問題第五講二維費(fèi)用的背包問題第六講 分組的背包問題第七講 有依賴的背包問題第八講泛化物品第九講 背包問題問法的變化附：USAC中的背包問題、八 、，刖言本篇文章是我（dd_engi）正在進(jìn)行中的一個(gè)雄心勃勃的寫作計(jì)劃的一部分，這個(gè) 計(jì)劃的內(nèi)容是寫作一份較為完善的 NOIP難度的動(dòng)態(tài)規(guī)劃總結(jié)，名為解動(dòng)態(tài)規(guī) 劃題的基本思考方式?，F(xiàn)在你看到的是這個(gè)寫作計(jì)劃最先發(fā)布的一部分。背包問題是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃模型。 它既簡單形象容易理解，又在某種程度上 能夠揭示動(dòng)態(tài)規(guī)劃的本質(zhì)，故不少教材都把它作為動(dòng)態(tài)規(guī)劃部分的第

2、一道例題， 我也將它放在我的寫作計(jì)劃的第一部分。讀本文最重要的是思考。因?yàn)槲业恼Z言和寫作方式向來不以易于理解為長， 思路 也偶有跳躍的地方，后面更有需要大量思考才能理解的比較抽象的內(nèi)容。 更重要 的是：不大量思考，絕對不可能學(xué)好動(dòng)態(tài)規(guī)劃這一信息學(xué)奧賽中最精致的部分。你現(xiàn)在看到的是本文的1.0正式版。我會(huì)長期維護(hù)這份文本，把大家的意見和建 議融入其中，也會(huì)不斷加入我在OI學(xué)習(xí)以及將來可能的ACM-ICPC勺征程中得到 的新的心得。但目前本文還沒有一個(gè)固定的發(fā)布頁面， 想了解本文是否有更新版 本發(fā)布，可以在OIBH論壇中以“背包問題九講”為關(guān)鍵字搜索貼子，每次比較 重大的版本更新都會(huì)在這里發(fā)貼公布

3、。目錄第一講01背包問題這是最基本的背包問題，每個(gè)物品最多只能放一次第二講完全背包問題第二個(gè)基本的背包問題模型，每種物品可以放無限多次。第三講多重背包問題每種物品有一個(gè)固定的次數(shù)上限。第四講混合三種背包問題將前面三種簡單的問題疊加成較復(fù)雜的問題。第五講二維費(fèi)用的背包問題一個(gè)簡單的常見擴(kuò)展。第六講 分組的背包問題一種題目類型，也是一個(gè)有用的模型。后兩節(jié)的基礎(chǔ)。第七講 有依賴的背包問題另一種給物品的選取加上限制的方法。第八講泛化物品我自己關(guān)于背包問題的思考成果，有一點(diǎn)抽象。第九講背包問題問法的變化試圖觸類旁通、舉一反三。附：USACOP的背包問題給出USACO Training上可供練習(xí)的背包問題

4、列表，及簡單的解答。聯(lián)系方式如果有任何意見和建議，特別是文章的錯(cuò)誤和不足，或者希望為文章添加新的材 料，可以通過這個(gè)網(wǎng)頁聯(lián)系我。致謝感謝以下名單：*阿坦* jason911* don glixp他們每人都最先指出了本文第一個(gè) beta版中的某個(gè)并非無關(guān)緊要的錯(cuò)誤。謝謝 你們?nèi)绱俗屑?xì)地閱讀拙作并彌補(bǔ)我的疏漏。感謝XiaQ，它針對本文的第一個(gè)beta版發(fā)表了用詞嚴(yán)厲的六條建議，雖然我只 認(rèn)同并采納了其中的兩條。在所有讀者幾乎一邊倒的贊揚(yáng)將我包圍的當(dāng)時(shí)， 你的 貼子是我的一劑清醒劑，讓我能清醒起來并用更嚴(yán)厲的眼光審視自己的作品。當(dāng)然，還有用各種方式對我表示鼓勵(lì)和支持的幾乎無法計(jì)數(shù)的同學(xué)。 不管是當(dāng)面

5、 贊揚(yáng)，或是在論壇上回復(fù)我的貼子，不管是發(fā)來熱情洋溢的郵件，或是在即時(shí)聊 天的窗口里豎起大拇指，你們的鼓勵(lì)和支持是支撐我的寫作計(jì)劃的強(qiáng)大動(dòng)力， 也 鞭策著我不斷提高自身水平，謝謝你們！最后，感謝Emacs這一世界最強(qiáng)大的編輯器的所有貢獻(xiàn)者，感謝它的插件 EmacsMuse的開發(fā)者們，本文的所有編輯工作都借助這兩個(gè)卓越的自由軟件完 成。謝謝你們一一自由軟件社群一一為社會(huì)提供了如此有生產(chǎn)力的工具。我深深欽佩你們身上體現(xiàn)出的自由軟件的精神， 沒有你們的感召，我不能完成本文。在 你們的影響下，采用自由文檔的方式發(fā)布本文檔， 也是我對自由社會(huì)事業(yè)的微薄 努力。P01: 01 背包問題題目有N件物品和一個(gè)

6、容量為V的背包。第i件物品的重量是ci，價(jià)值是wi。 求解將哪些物品裝入背包可使價(jià)值總和最大?；舅悸愤@是最基礎(chǔ)的背包問題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)： 即 fiv 表示前 i 件物品恰放入一個(gè)容量為 v 的背包可以 獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：fiv=maxfi-1v,fi-1v-ci+wi這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的。 所以有必要將它詳細(xì)解釋一下： “將前 i 件物品放入容量為 v 的背包中”這個(gè)子 問題，若只考慮第 i 件物品的策略 (放或不放)， 那么就可以轉(zhuǎn)化為一個(gè)只牽扯 前 i-1 件物品的問題。

7、如果不放第 i 件物品，那么問題就轉(zhuǎn)化為“前 i-1 件物品 放入容量為 v 的背包中”，價(jià)值為 fi-1v ；如果放第 i 件物品，那么問題就 轉(zhuǎn)化為“前 i-1 件物品放入剩下的容量為 v-ci 的背包中”，此時(shí)能獲得的最 大價(jià)值就是 fi-1v-ci 再加上通過放入第 i 件物品獲得的價(jià)值 wi 。優(yōu)化空間復(fù)雜度以上方法的時(shí)間和空間復(fù)雜度均為O(N*V)，其中時(shí)間復(fù)雜度基本已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以優(yōu)化到 O(V)。先考慮上面講的基本思路如何實(shí)現(xiàn)，肯定是有一個(gè)主循環(huán)i=1.N ，每次算出來二維數(shù)組 fi0.V的所有值。 那么， 如果只用一個(gè)數(shù)組 f0.V，能不能保證第i次循環(huán)結(jié)

8、束后fv中表示的就是我們定義的狀態(tài)fiv 呢？ fiv 是由 fi-1v 和 fi-1v-ci 兩個(gè)子問題遞推而來， 能否保證在推 fiv 時(shí)(也 即在第 i 次主循環(huán)中推 fv 時(shí))能夠得到 fi-1v 和 fi-1v-ci 的值呢？ 事實(shí)上，這要求在每次主循環(huán)中我們以v=V.0 的順序推 fv ，這樣才能保證推fv 時(shí) fv-ci 保存的是狀態(tài) fi-1v-ci 的值。偽代碼如下：for i=1.Nfor v=V.0fv=maxfv,fv-ci+wi;其中的 fv=maxfv,fv-ci一句恰就相當(dāng)于我們的轉(zhuǎn)移方程fiv=maxfi-1v,fi-1v-ci，因?yàn)楝F(xiàn)在的 fv-ci 就相當(dāng)于

9、原來的fi-1v-ci 。如果將v的循環(huán)順序從上面的逆序改成順序的話，那么 則成了 fiv 由 fiv-ci 推知，與本題意不符， 但它卻是另一個(gè)重要的背包問題P02最簡捷的解決方案，故學(xué)習(xí)只用一維數(shù)組解01背包問題是十分必要的。事實(shí)上，使用一維數(shù)組解01背包的程序在后面會(huì)被多次用到，所以這里抽象出 一個(gè)處理一件01背包中的物品過程，以后的代碼中直接調(diào)用不加說明。過程ZeroOnePacK表示處理一件01背包中的物品，兩個(gè)參數(shù) cost、weight分 別表明這件物品的費(fèi)用和價(jià)值。procedure ZeroOn ePack(cost,weight)for v=V.costfv=max fv,

10、fv-cost+weight 注意這個(gè)過程里的處理與前面給出的偽代碼有所不同。前面的示例程序?qū)懗?v=V.0是為了在程序中體現(xiàn)每個(gè)狀態(tài)都按照方程求解了，避免不必要的思維復(fù) 雜度。而這里既然已經(jīng)抽象成看作黑箱的過程了，就可以加入優(yōu)化。費(fèi)用為cost的物品不會(huì)影響狀態(tài)f0.cost-1，這是顯然的。有了這個(gè)過程以后，01背包問題的偽代碼就可以這樣寫：for i=1.NZero On ePack(ci,wi);初始化的細(xì)節(jié)問題我們看到的求最優(yōu)解的背包問題題目中，事實(shí)上有兩種不太相同的問法。有的題目要求“恰好裝滿背包”時(shí)的最優(yōu)解，有的題目則并沒有要求必須把背包裝滿。 一種區(qū)別這兩種問法的實(shí)現(xiàn)方法是在初

11、始化的時(shí)候有所不同。如果是第一種問法，要求恰好裝滿背包，那么在初始化時(shí)除了 f0為0其它 f1.V均設(shè)為-X,這樣就可以保證最終得到的fN是一種恰好裝滿背包的最 優(yōu)解。如果并沒有要求必須把背包裝滿，而是只希望價(jià)格盡量大，初始化時(shí)應(yīng)該將f0.V全部設(shè)為0。為什么呢？可以這樣理解：初始化的f數(shù)組事實(shí)上就是在沒有任何物品可以放入 背包時(shí)的合法狀態(tài)。如果要求背包恰好裝滿，那么此時(shí)只有容量為0的背包可能 被價(jià)值為0的nothing “恰好裝滿”，其它容量的背包均沒有合法的解，屬于未 定義的狀態(tài)，它們的值就都應(yīng)該是-%了。如果背包并非必須被裝滿，那么任何 容量的背包都有一個(gè)合法解“什么都不裝”，這個(gè)解的價(jià)

12、值為 0,所以初始時(shí)狀 態(tài)的值也就全部為0 了。這個(gè)小技巧完全可以推廣到其它類型的背包問題，后面也就不再對進(jìn)行狀態(tài)轉(zhuǎn)移 之前的初始化進(jìn)行講解。小結(jié)01背包問題是最基本的背包問題，它包含了背包問題中設(shè)計(jì)狀態(tài)、方程的最基 本思想，另外，別的類型的背包問題往往也可以轉(zhuǎn)換成 01背包問題求解。故一 定要仔細(xì)體會(huì)上面基本思路的得出方法， 狀態(tài)轉(zhuǎn)移方程的意義，以及最后怎樣優(yōu) 化的空間復(fù)雜度。首頁P(yáng)02:完全背包問題題目有N種物品和一個(gè)容量為V的背包，每種物品都有無限件可用。第i種物品的費(fèi) 用是ci，價(jià)值是wi。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不 超過背包容量，且價(jià)值總和最大?；舅悸愤@個(gè)問題非

13、常類似于01背包問題，所不同的是每種物品有無限件。也就是從每 種物品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取0件、取1件、取2件,，等很多種。如果仍然按照解01背包時(shí)的思路，令fiv 表示前i種物品恰放入一個(gè)容量為v的背包的最大權(quán)值。仍然可以按照每種物品不同 的策略寫出狀態(tài)轉(zhuǎn)移方程，像這樣：fiv=maxfi-1v-k*ci+k*wi|0<=k*civ=v這跟01背包問題一樣有O(N*V)個(gè)狀態(tài)需要求解，但求解每個(gè)狀態(tài)的時(shí)間已經(jīng)不 是常數(shù)了，求解狀態(tài)fiv 的時(shí)間是O(v/ci)，總的復(fù)雜度是超過 O(VN)的。將01背包問題的基本思路加以改進(jìn)，得到了這樣一個(gè)清晰的方法。這

14、說明 01 背包問題的方程的確是很重要，可以推及其它類型的背包問題。 但我們還是試圖 改進(jìn)這個(gè)復(fù)雜度。一個(gè)簡單有效的優(yōu)化完全背包問題有一個(gè)很簡單有效的優(yōu)化，是這樣的：若兩件物品i、j滿足ci<=cj 且wi>=wj，則將物品j去掉，不用考慮。這個(gè)優(yōu)化的正確性顯 然：任何情況下都可將價(jià)值小費(fèi)用高得j換成物美價(jià)廉的i，得到至少不會(huì)更差 的方案。對于隨機(jī)生成的數(shù)據(jù)，這個(gè)方法往往會(huì)大大減少物品的件數(shù)，從而加快速度。然而這個(gè)并不能改善最壞情況的復(fù)雜度，因?yàn)橛锌赡芴貏e設(shè)計(jì)的數(shù)據(jù)可以一件物品也去不掉。這個(gè)優(yōu)化可以簡單的O(NT)地實(shí)現(xiàn)，一般都可以承受。另外，針對背包問題而 言，比較不錯(cuò)的一種方法

15、是：首先將費(fèi)用大于V的物品去掉，然后使用類似計(jì)數(shù) 排序的做法，計(jì)算出費(fèi)用相同的物品中價(jià)值最高的是哪個(gè)，可以O(shè)(V+N地完成這個(gè)優(yōu)化。這個(gè)不太重要的過程就不給出偽代碼了，希望你能獨(dú)立思考寫出偽代碼或程序。轉(zhuǎn)化為01背包問題求解既然01背包問題是最基本的背包問題，那么我們可以考慮把完全背包問題轉(zhuǎn)化 為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/ci件，于 是可以把第i種物品轉(zhuǎn)化為V/ci件費(fèi)用及價(jià)值均不變的物品，然后求解這個(gè) 01背包問題。這樣完全沒有改進(jìn)基本思路的時(shí)間復(fù)雜度，但這畢竟給了我們將 完全背包問題轉(zhuǎn)化為01背包問題的思路：將一種物品拆成多件物品。更高效的轉(zhuǎn)化方法是：把第

16、i種物品拆成費(fèi)用為ci*2Ak 、價(jià)值為wi*2Ak的 若干件物品，其中k滿足ci*2Ak<=V。這是二進(jìn)制的思想，因?yàn)椴还茏顑?yōu)策略 選幾件第i種物品，總可以表示成若干個(gè)2Ak件物品的和。這樣把每種物品拆成 O(log(V/ci)件物品，是一個(gè)很大的改進(jìn)。但我們有更優(yōu)的O(VN)的算法。O(VN)的算法這個(gè)算法使用一維數(shù)組，先看偽代碼：for i=1.Nfor v=0.Vfv=maxfv,fv-cost+weight你會(huì)發(fā)現(xiàn)，這個(gè)偽代碼與P01的偽代碼只有v的循環(huán)次序不同而已。為什么這樣 一改就可行呢？首先想想為什么 P01中要按照v=V.O的逆序來循環(huán)。這是因?yàn)?要保證第i次循環(huán)中的狀

17、態(tài)fiv是由狀態(tài)fi-1v-ci遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時(shí)，依據(jù)的是一個(gè)絕無已經(jīng)選入第i件物品的子結(jié)果fi-1v-ci 。而現(xiàn) 在完全背包的特點(diǎn)恰是每種物品可選無限件，所以在考慮“加選一件第 i種物 品”這種策略時(shí)，卻正需要一個(gè)可能已選入第i種物品的子結(jié)果fiv-ci，所以就可以并且必須采用v=0.V的順序循環(huán)。這就是這個(gè)簡單的程序?yàn)楹纬闪?的道理。這個(gè)算法也可以以另外的思路得出。例如，基本思路中的狀態(tài)轉(zhuǎn)移方程可以等價(jià)地變形成這種形式：fiv=maxfi-1v,fiv-ci+wi將這個(gè)方程用一維數(shù)組實(shí)現(xiàn)，便得到了上面的偽代碼。最后

18、抽象出處理一件完全背包類物品的過程偽代碼，以后會(huì)用到：procedure CompletePack(cost,weight)for v=cost.Vfv=maxfv,fv-ci+wi總結(jié)完全背包問題也是一個(gè)相當(dāng)基礎(chǔ)的背包問題，它有兩個(gè)狀態(tài)轉(zhuǎn)移方程，分別在“基本思路”以及“ O(VN)的算法“的小節(jié)中給出。希望你能夠?qū)@兩個(gè)狀態(tài)轉(zhuǎn)移方程都仔細(xì)地體會(huì)，不僅記住，也要弄明白它們是怎么得出來的，最好能夠自 己想一種得到這些方程的方法。事實(shí)上，對每一道動(dòng)態(tài)規(guī)劃題目都思考其方程的 意義以及如何得來，是加深對動(dòng)態(tài)規(guī)劃的理解、提高動(dòng)態(tài)規(guī)劃功力的好方法。首頁P(yáng)03:多重背包問題題目有N種物品和一個(gè)容量為V的背包

19、。第i種物品最多有ni件可用，每件費(fèi)用 是ci，價(jià)值是wi。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超 過背包容量，且價(jià)值總和最大。基本算法這題目和完全背包問題很類似。基本的方程只需將完全背包問題的方程略微一改 即可，因?yàn)閷τ诘趇種物品有ni+1種策略：取0件，取1件,，取 ni件。 令fiv 表示前i種物品恰放入一個(gè)容量為v的背包的最大權(quán)值，則有狀態(tài)轉(zhuǎn) 移方程：fiv=maxfi-1v-k*ci+k*wi|0<=k<二 ni復(fù)雜度是O(V*X ni)。轉(zhuǎn)化為01背包問題另一種好想好寫的基本方法是轉(zhuǎn)化為01背包求解：把第i種物品換成ni件01背包中的物品，則得到了物品數(shù)為工n

20、i的01背包問題，直接求解，復(fù)雜度仍然是 O(V*X ni)。但是我們期望將它轉(zhuǎn)化為01背包問題之后能夠像完全背包一樣降低復(fù)雜度。仍 然考慮二進(jìn)制的思想，我們考慮把第i種物品換成若干件物品，使得原問題中第 i種物品可取的每種策略一一取 0.ni件一一均能等價(jià)于取若干件代換以后的 物品。另外，取超過ni件的策略必不能出現(xiàn)。方法是：將第i種物品分成若干件物品，其中每件物品有一個(gè)系數(shù)，這件物品的 費(fèi)用和價(jià)值均是原來的費(fèi)用和價(jià)值乘以這個(gè)系數(shù)。使這些系數(shù)分別為1,2,4,.,2八(心1),ni-2Ak+1，且k是滿足n口-2你+1>0的最大整數(shù)。例如，如果ni為13,就將這種物品分成系數(shù)分別為1,

21、2,4,6的四件物品。分成的這幾件物品的系數(shù)和為ni，表明不可能取多于ni件的第i種物品。 另外這種方法也能保證對于0. ni間的每一個(gè)整數(shù)，均可以用若干個(gè)系數(shù)的和 表示，這個(gè)證明可以分0.2Ak-1和2Ak.ni兩段來分別討論得出，并不難, 希望你自己思考嘗試一下。這樣就將第i種物品分成了 O(log ni)種物品，將原問題轉(zhuǎn)化為了復(fù)雜度為O(V*X log ni) 的01背包問題，是很大的改進(jìn)。下面給出O(log amount)時(shí)間處理一件多重背包中物品的過程，其中amount表示物品的數(shù)量：procedure MultiplePack(cost,weight,am ount)if cos

22、t*am oun t>=VCompletePack(cost,weight)returnin teger k=1while k< numZeroO nePack(k*cost,k*weight)amoun t=am oun t-kk=k*2Zero On ePack(am oun t*cost,amou nt*weight)希望你仔細(xì)體會(huì)這個(gè)偽代碼，如果不太理解的話，不妨翻譯成程序代碼以后，單 步執(zhí)行幾次，或者頭腦加紙筆模擬一下，也許就會(huì)慢慢理解了。O(VN)的算法多重背包問題同樣有O(VN)的算法。這個(gè)算法基于基本算法的狀態(tài)轉(zhuǎn)移方程，但 應(yīng)用單調(diào)隊(duì)列的方法使 每個(gè)狀態(tài)的值可以以均

23、攤 O(1)的時(shí)間求解。由于用單調(diào) 隊(duì)列優(yōu)化的DP已超出了 NOIP的范圍，故本文不再展開講解。我最初了解到這個(gè) 方法是在樓天成的“男人八題”幻燈片上。小結(jié)這里我們看到了將一個(gè)算法的復(fù)雜度由O(V*X ni)改進(jìn)到O(V*X log ni) 的過程，還知道了存在應(yīng)用超出 NOIP范圍的知識(shí)的O(VN算法。希望你特別注意“拆分物品”的思想和方法，自己證明一下它的正確性，并將完整的程序代碼寫 出來。首頁P(yáng)04:混合三種背包問題冋題如果將P01、P02、P03混合起來。也就是說，有的物品只可以取一次(01背包)， 有的物品可以取無限次(完全背包)，有的物品可以取的次數(shù)有一個(gè)上限 (多重 背包)。應(yīng)該

24、怎么求解呢？01背包與完全背包的混合考慮到在P01和P02中給出的偽代碼只有一處不同，故如果只有兩類物品：一類 物品只能取一次，另一類物品可以取無限次，那么只需在對每個(gè)物品應(yīng)用轉(zhuǎn)移方 程時(shí)，根據(jù)物品的類別選用順序或逆序的循環(huán)即可，復(fù)雜度是O(VN)。偽代碼如下：for i=1.Nif 第i件物品是01背包for v=V.0fv=maxfv,fv-ci+wi;else if 第i件物品是完全背包for v=0.Vfv=maxfv,fv-ci+wi;再加上多重背包如果再加上有的物品最多可以取有限次，那么原則上也可以給出0(VN)的解法：遇到多重背包類型的物品用單調(diào)隊(duì)列解即可。但如果不考慮超過NOI

25、P范圍的算法的話，用P03中將每個(gè)這類物品分成O(log ni) 個(gè)01背包的物品的方法也 已經(jīng)很優(yōu)了。當(dāng)然，更清晰的寫法是調(diào)用我們前面給出的三個(gè)相關(guān)過程。for i=1.Nif 第i件物品是01背包ZeroO nePack(ci,wi)else if第i件物品是完全背包CompletePack(ci,wi)else if第i件物品是多重背包MultiplePack(ci,wi, n i)在最初寫出這三個(gè)過程的時(shí)候，可能完全沒有想到它們會(huì)在這里混合應(yīng)用。我想這體現(xiàn)了編程中抽象的威力。如果你一直就是以這種“抽象出過程”的方式寫每 一類背包問題的，也非常清楚它們的實(shí)現(xiàn)中細(xì)微的不同，那么在遇到混合三

26、種背包問題的題目時(shí)，一定能很快想到上面簡潔的解法，對嗎？小結(jié)有人說，困難的題目都是由簡單的題目疊加而來的。 這句話是否公理暫且存之不 論，但它在本講中已經(jīng)得到了充分的體現(xiàn)。本來 01背包、完全背包、多重背包 都不是什么難題，但將它們簡單地組合起來以后就得到了這樣一道一定能嚇倒不 少人的題目。但只要基礎(chǔ)扎實(shí)，領(lǐng)會(huì)三種基本背包問題的思想， 就可以做到把困 難的題目拆分成簡單的題目來解決。首頁P(yáng)05:二維費(fèi)用的背包問題問題二維費(fèi)用的背包問題是指：對于每件物品，具有兩種不同的費(fèi)用；選擇這件物品 必須同時(shí)付出這兩種代價(jià)；對于每種代價(jià)都有一個(gè)可付出的最大值 （背包容量）。 問怎樣選擇物品可以得到最大的價(jià)值

27、。設(shè)這兩種代價(jià)分別為代價(jià)1和代價(jià)2,第i件物品所需的兩種代價(jià)分別為 ai和bi。兩種代價(jià)可付出的最大值（兩種 背包容量）分別為V和UL物品的價(jià)值為wi。算法費(fèi)用加了一維，只需狀態(tài)也加一維即可。設(shè)fivu 表示前i件物品付出兩種代價(jià)分別為v和u時(shí)可獲得的最大價(jià)值。狀態(tài)轉(zhuǎn)移方程就是：fivu=maxfi-1vu,fi-1v-aiu-bi+wi如前述方法，可以只使用二維的數(shù)組：當(dāng)每件物品只可以取一次時(shí)變量V和u采用逆序的循環(huán)，當(dāng)物品有如完全背包問題時(shí)采用順序的循環(huán)。當(dāng)物品有如多重背包問題時(shí)拆分物品。這里就不再給出偽代碼了，相信有了前面的基礎(chǔ)，你能夠 自己實(shí)現(xiàn)出這個(gè)問題的程序。物品總個(gè)數(shù)的限制（精辟）

28、有時(shí)，“二維費(fèi)用”的條件是以這樣一種隱含的方式給出的：最多只能取M件物品。這事實(shí)上相當(dāng)于每件物品多了一種“件數(shù)”的費(fèi)用，每個(gè)物品的件數(shù)費(fèi)用均為1,可以付出的最大件數(shù)費(fèi)用為 M換句話說，設(shè)fvm表示付出費(fèi)用V、最 多選m件時(shí)可得到的最大價(jià)值，則根據(jù)物品的類型（01、完全、多重）用不同的 方法循環(huán)更新，最后在f0.V0.M范圍內(nèi)尋找答案。小結(jié)當(dāng)發(fā)現(xiàn)由熟悉的動(dòng)態(tài)規(guī)劃題目變形得來的題目時(shí)，在原來的狀態(tài)中加一緯以滿足新的限制是一種比較通用的方法。希望你能從本講中初步體會(huì)到這種方法。首頁P(yáng)06:分組的背包問題冋題有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是ci，價(jià)值是wi。 這些物品被劃分為若干組，

29、每組中的物品互相沖突，最多選一件。求解將哪些物 品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。算法這個(gè)問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選 也就是說設(shè)fkv表示前k組物品花費(fèi)費(fèi)用v能取得的最大權(quán)值，則有：fkv=maxfk-1v,fk-1v-ci+wi|物品 i 屬于第 k 組使用一維數(shù)組的偽代碼如下：for所有的組kfor v=V.0for 所有的i屬于組kfv=maxfv,fv-ci+wi注意這里的三層循環(huán)的順序，甚至在本文的 beta版中我自己都寫錯(cuò)了?！癴orv=V.0 ”這一層循環(huán)必須在“for所有的i屬于組k”之外。這樣才能保證每-

30、組內(nèi)的物品最多只有一個(gè)會(huì)被添加到背包中。另外，顯然可以對每組內(nèi)的物品應(yīng)用 P02中“一個(gè)簡單有效的優(yōu)化”小結(jié)分組的背包問題將彼此互斥的若干物品稱為一個(gè)組，這建立了一個(gè)很好的模型。不少背包問題的變形都可以轉(zhuǎn)化為分組的背包問題（例如P07），由分組的背包問題進(jìn)一步可定義“泛化物品”的概念，十分有利于解題。首頁P(yáng)07:有依賴的背包問題簡化的冋題這種背包問題的物品間存在某種“依賴”的關(guān)系。也就是說，i依賴于j，表示 若選物品i，則必須選物品j。為了簡化起見，我們先設(shè)沒有某個(gè)物品既依賴于 別的物品，又被別的物品所依賴；另外，沒有某件物品同時(shí)依賴多件物品。算法這個(gè)問題由NOIP2006金明的預(yù)算方案一題擴(kuò)

31、展而來。遵從該題的提法，將不依 賴于別的物品的物品稱為“主件”， 依賴于某主件的物品稱為“附件”。由這個(gè)問題的簡化條件可知所有的物品由若干主件和依賴于每個(gè)主件的一個(gè)附件集合 組成。按照背包問題的一般思路，僅考慮一個(gè)主件和它的附件集合?？墒?，可用的策略非常多，包括：一個(gè)也不選，僅選擇主件，選擇主件后再選擇一個(gè)附件，選擇主 件后再選擇兩個(gè)附件,無法用狀態(tài)轉(zhuǎn)移方程來表示如此多的策略。（事實(shí)上， 設(shè)有n個(gè)附件，則策略有2An+1個(gè)，為指數(shù)級(jí)。）考慮到所有這些策略都是互斥的（也就是說，你只能選擇一種策略），所以一個(gè) 主件和它的附件集合實(shí)際上對應(yīng)于 P06中的一個(gè)物品組，每個(gè)選擇了主件又選擇 了若干個(gè)附件

32、的策略對應(yīng)于這個(gè)物品組中的一個(gè)物品，其費(fèi)用和價(jià)值都是這個(gè)策 略中的物品的值的和。但僅僅是這一步轉(zhuǎn)化并不能給出一個(gè)好的算法， 因?yàn)槲锲?組中的物品還是像原冋題的策略一樣多。再考慮P06中的一句話： 可以對每組中的物品應(yīng)用 P02中“一個(gè)簡單有效的優(yōu) 化”。這提示我們，對于一個(gè)物品組中的物品，所有費(fèi)用相同的物品只留一個(gè) 價(jià)值最大的，不影響結(jié)果。所以，我們可以對主件i的“附件集合”先進(jìn)行一次 01背包，得到費(fèi)用依次為O.V-ci 所有這些值時(shí)相應(yīng)的最大價(jià)值 f0.V-ci。那么這個(gè)主件及它的附件集合相當(dāng)于 V-ci+1個(gè)物品的物品組，其中費(fèi)用為ci+k的物品的價(jià)值為fk+wi。也就是說原來指數(shù)級(jí)的策

33、 略中有很多策略都是冗余的，通過一次 01背包后，將主件i轉(zhuǎn)化為V-ci+1 個(gè)物品的物品組，就可以直接應(yīng)用 P06的算法解決問題了。較一般的問題更一般的問題是：依賴關(guān)系以圖論中“森林”的形式給出（森林即多叉樹的集 合），也就是說，主件的附件仍然可以具有自己的附件集合，限制只是每個(gè)物品最多只依賴于一個(gè)物品（只有一個(gè)主件）且不出現(xiàn)循環(huán)依賴。解決這個(gè)問題仍然可以用將每個(gè)主件及其附件集合轉(zhuǎn)化為物品組的方式。唯一不同的是，由于附件可能還有附件，就不能將每個(gè)附件都看作一個(gè)一般的 01背包 中的物品了。若這個(gè)附件也有附件集合，則它必定要被先轉(zhuǎn)化為物品組，然后用 分組的背包問題解出主件及其附件集合所對應(yīng)的附

34、件組中各個(gè)費(fèi)用的附件所對 應(yīng)的價(jià)值。事實(shí)上，這是一種樹形DP其特點(diǎn)是每個(gè)父節(jié)點(diǎn)都需要對它的各個(gè)兒子的屬性 進(jìn)行一次DP以求得自己的相關(guān)屬性。這已經(jīng)觸及到了 “泛化物品”的思想?？?完P(guān)08后，你會(huì)發(fā)現(xiàn)這個(gè)“依賴關(guān)系樹”每一個(gè)子樹都等價(jià)于一件泛化物品，求某節(jié)點(diǎn)為根的子樹對應(yīng)的泛化物品相當(dāng)于求其所有兒子的對應(yīng)的泛化物品之和。小結(jié)NOIP2006的那道背包問題我做得很失敗，寫了上百行的代碼，卻一分未得。后 來我通過思考發(fā)現(xiàn)通過引入“物品組”和“依賴”的概念可以加深對這題的理 解,還可以解決它的推廣問題。用物品組的思想考慮那題中極其特殊的依賴關(guān)系： 物品不能既作主件又作附件，每個(gè)主件最多有兩個(gè)附件，可

35、以發(fā)現(xiàn)一個(gè)主件和它 的兩個(gè)附件等價(jià)于一個(gè)由四個(gè)物品組成的物品組，這便揭示了問題的某種本質(zhì)。我想說：失敗不是什么丟人的事情，從失敗中全無收獲才是。首頁P(yáng)08:泛化物品定義考慮這樣一種物品，它并沒有固定的費(fèi)用和價(jià)值，而是它的價(jià)值隨著你分配給它 的費(fèi)用而變化。這就是泛化物品的概念。更嚴(yán)格的定義之。在背包容量為V的背包問題中，泛化物品是一個(gè)定義域?yàn)?.V 中的整數(shù)的函數(shù)h,當(dāng)分配給它的費(fèi)用為V時(shí)，能得到的價(jià)值就是h(v)。這個(gè)定義有一點(diǎn)點(diǎn)抽象，另一種理解是一個(gè)泛化物品就是一個(gè)數(shù)組h0.V，給它費(fèi)用v,可得到價(jià)值hV。一個(gè)費(fèi)用為c價(jià)值為w的物品，如果它是01背包中的物品，那么把它看成泛化 物品，它就是除

36、了 h(c)=w其它函數(shù)值都為0的一個(gè)函數(shù)。如果它是完全背包中 的物品，那么它可以看成這樣一個(gè)函數(shù)，僅當(dāng)v被c整除時(shí)有h(v)=v/c*w，其它函數(shù)值均為0。如果它是多重背包中重復(fù)次數(shù)最多為n的物品，那么它對應(yīng)的泛化物品的函數(shù)有h(v)=v/c*w 僅當(dāng)v被c整除且v/c<=n，其它情況函數(shù)值均為 0。一個(gè)物品組可以看作一個(gè)泛化物品h0對于一個(gè)0.V中的v，若物品組中不存在費(fèi)用為v的的物品，貝U h(v)=0，否則h(v)為所有費(fèi)用為v的物品的最大價(jià)值。 P07中每個(gè)主件及其附件集合等價(jià)于一個(gè)物品組，自然也可看作一個(gè)泛化物品。泛化物品的和如果面對兩個(gè)泛化物品h和I ,要用給定的費(fèi)用從這兩

37、個(gè)泛化物品中得到最大的 價(jià)值，怎么求呢？事實(shí)上，對于一個(gè)給定的費(fèi)用v,只需枚舉將這個(gè)費(fèi)用如何分配給兩個(gè)泛化物品就可以了。同樣的，對于0.V的每一個(gè)整數(shù)v,可以求得費(fèi)用v分配到h和I中的最大價(jià)值f(v)。也即f(v)=maxh(k)+l(v-k)|0<=kv=v可以看到，f也是一個(gè)由泛化物品h和I決定的定義域?yàn)?.V的函數(shù)，也就是 說，f是一個(gè)由泛化物品h和I決定的泛化物品。由此可以定義泛化物品的和：h、l都是泛化物品，若泛化物品f滿足 f(v)=maxh(k)+l(v-k)|0<=k<=v ，則稱 f 是 h 與 l 的和，即 f=h+l。這個(gè)運(yùn)算 的時(shí)間復(fù)雜度取決于背包的容

38、量，是0(V9)。泛化物品的定義表明：在一個(gè)背包問題中，若將兩個(gè)泛化物品代以它們的和， 不 影響問題的答案。事實(shí)上，對于其中的物品都是泛化物品的背包問題，求它的答案的過程也就是求所有這些泛化物品之和的過程。設(shè)此和為s,則答案就是s0.V中的最大值。背包問題的泛化物品一個(gè)背包問題中，可能會(huì)給出很多條件，包括每種物品的費(fèi)用、價(jià)值等屬性，物 品之間的分組、依賴等關(guān)系等。但肯定能將問題對應(yīng)于某個(gè)泛化物品。 也就是說， 給定了所有條件以后，就可以對每個(gè)非負(fù)整數(shù) V求得：若背包容量為V,將物品 裝入背包可得到的最大價(jià)值是多少，這可以認(rèn)為是定義在非負(fù)整數(shù)集上的一件泛 化物品。這個(gè)泛化物品一一或者說問題所對應(yīng)

39、的一個(gè)定義域?yàn)榉秦?fù)整數(shù)的函數(shù) 包含了關(guān)于問題本身的高度濃縮的信息。一般而言，求得這個(gè)泛化物品的一 個(gè)子域（例如0.V ）的值之后，就可以根據(jù)這個(gè)函數(shù)的取值得到背包問題的最 終答案。綜上所述，一般而言，求解背包問題，即求解這個(gè)問題所對應(yīng)的一個(gè)函數(shù)， 即該 問題的泛化物品。而求解某個(gè)泛化物品的一種方法就是將它表示為若干泛化物品 的和然后求之。小結(jié)本講可以說都是我自己的原創(chuàng)思想。具體來說，是我在學(xué)習(xí)函數(shù)式編程的Scheme 語言時(shí)，用函數(shù)編程的眼光審視各類背包問題得出的理論。這一講真的很抽象， 也許在“模型的抽象程度”這一方面已經(jīng)超出了 NOIP的要求，所以暫且看不懂 也沒關(guān)系。相信隨著你的OI之路

40、逐漸延伸，有一天你會(huì)理解的。我想說：“思考”是一個(gè) OIer最重要的品質(zhì)。簡單的問題，深入思考以后，也 能發(fā)現(xiàn)更多。首頁P(yáng)09: 背包問題問法的變化 以上涉及的各種背包問題都是要求在背包容量 （費(fèi)用）的限制下求可以取到的最 大價(jià)值，但背包問題還有很多種靈活的問法，在這里值得提一下。但是我認(rèn)為， 只要深入理解了求背包問題最大價(jià)值的方法， 即使問法變化了， 也是不難想出算 法的。例如，求解最多可以放多少件物品或者最多可以裝滿多少背包的空間。 這都可以 根據(jù)具體問題利用前面的方程求出所有狀態(tài)的值（ f 數(shù)組）之后得到。還有，如果要求的是“總價(jià)值最小”“總件數(shù)最小”， 只需簡單的將上面的狀態(tài) 轉(zhuǎn)移方程

41、中的max改成min即可。下面說一些變化更大的問法。輸出方案一般而言， 背包問題是要求一個(gè)最優(yōu)值， 如果要求輸出這個(gè)最優(yōu)值的方案， 可以 參照一般動(dòng)態(tài)規(guī)劃問題輸出方案的方法： 記錄下每個(gè)狀態(tài)的最優(yōu)值是由狀態(tài)轉(zhuǎn)移 方程的哪一項(xiàng)推出來的， 換句話說， 記錄下它是由哪一個(gè)策略推出來的。 便可根 據(jù)這條策略找到上一個(gè)狀態(tài)，從上一個(gè)狀態(tài)接著向前推即可。還是以 01 背包為例，方程為 fiv=maxfi-1v,fi-1v-ci+wi。再用一個(gè)數(shù)組 giv ，設(shè) giv=0 表示推出 fiv 的值時(shí)是采用了方程的 前一項(xiàng)（也即 fiv=fi-1v）， giv 表示采用了方程的后一項(xiàng)。注意這兩項(xiàng)分別表示了兩種

42、策略： 未選第 i 個(gè)物品及選了第 i 個(gè)物品。 那么輸出方案 的偽代碼可以這樣寫（設(shè)最終狀態(tài)為 fNV ）：i=N v=V while（i>0） if（giv=0） print "未選第 i 項(xiàng)物品"else if（giv=1）print "選了第 i 項(xiàng)物品"v=v-ci 另外，采用方程的前一項(xiàng)或后一項(xiàng)也可以在輸出方案的過程中根據(jù) fiv 的值 實(shí)時(shí)地求出來，也即不須紀(jì)錄 g 數(shù)組，將上述代碼中的 giv=0 改成 fiv=fi-1v，giv=1 改成 fiv=fi-1v-ci+wi也可。輸出字典序最小的最優(yōu)方案 這里“字典序最小”的意思是 1

43、.N 號(hào)物品的選擇方案排列出來以后字典序最 小。以輸出 01 背包最小字典序的方案為例。一般而言， 求一個(gè)字典序最小的最優(yōu)方案， 只需要在轉(zhuǎn)移時(shí)注意策略。 首先，子 問題的定義要略改一些。 我們注意到， 如果存在一個(gè)選了物品 1 的最優(yōu)方案，那 么答案一定包含物品 1，原問題轉(zhuǎn)化為一個(gè)背包容量為 v-c1 ，物品為 2.N 的 子問題。反之，如果答案不包含物品1,則轉(zhuǎn)化成背包容量仍為 V,物品為2.N 的子問題。 不管答案怎樣， 子問題的物品都是以 i.N 而非前所述的 1.i 的形式 來定義的， 所以狀態(tài)的定義和轉(zhuǎn)移方程都需要改一下。 但也許更簡易的方法是先 把物品逆序排列一下，以下按物品已

44、被逆序排列來敘述。在這種情況下， 可以按照前面經(jīng)典的狀態(tài)轉(zhuǎn)移方程來求值， 只是輸出方案的時(shí)候 要注意：從 N 到 1 輸入時(shí)，如果 fiv=fi-v 及fiv=fi-1f-ci+wi同時(shí)成立，應(yīng)該按照后者（即選擇了物品 i ）來輸出方案。求方案總數(shù) 對于一個(gè)給定了背包容量、物品費(fèi)用、物品間相互關(guān)系（分組、依賴等）的背包 問題，除了再給定每個(gè)物品的價(jià)值后求可得到的最大價(jià)值外， 還可以得到裝滿背 包或?qū)⒈嘲b至某一指定容量的方案總數(shù)。對于這類改變問法的問題，一般只需將狀態(tài)轉(zhuǎn)移方程中的 max改成sum即可。例 如若每件物品均是完全背包中的物品，轉(zhuǎn)移方程即為fiv=sumfi-1v,fiv-ci初始

45、條件 f00=1 。事實(shí)上，這樣做可行的原因在于狀態(tài)轉(zhuǎn)移方程已經(jīng)考察了所有可能的背包組成方 案。最優(yōu)方案的總數(shù)這里的最優(yōu)方案是指物品總價(jià)值最大的方案。以 01 背包為例。結(jié)合求最大總價(jià)值和方案總數(shù)兩個(gè)問題的思路，最優(yōu)方案的總數(shù)可以這樣求： fiv 意義同前述， giv 表示這個(gè)子問題的最優(yōu)方案的總數(shù)， 則在求 fiv 的同時(shí)求 giv 的偽代碼如下：for i=1.Nfor v=0.V fiv=maxfi-1v,fi-1v-ci+wi giv=0 if(fiv=fi-1v) inc(giv,gi-1v if(fiv=fi-1v-ci+wi) inc(giv,gi-1v-ci)如果你是第一次看到

46、這樣的問題，請仔細(xì)體會(huì)上面的偽代碼。求次優(yōu)解、第K優(yōu)解對于求次優(yōu)解、第K優(yōu)解類的問題，如果相應(yīng)的最優(yōu)解問題能寫出狀態(tài)轉(zhuǎn)移方程、 用動(dòng)態(tài)規(guī)劃解決，那么求次優(yōu)解往往可以相同的復(fù)雜度解決， 第K優(yōu)解則比求最 優(yōu)解的復(fù)雜度上多一個(gè)系數(shù)K。其基本思想是將每個(gè)狀態(tài)都表示成有序隊(duì)列，將狀態(tài)轉(zhuǎn)移方程中的max/min轉(zhuǎn)化成有序隊(duì)列的合并。這里仍然以01背包為例講解一下。首先看01背包求最優(yōu)解的狀態(tài)轉(zhuǎn)移方程：fiv=maxfi-1v,fi-1v-ci+wi。如果要求第 K優(yōu)解，那么狀態(tài)fiv就應(yīng)該是一個(gè)大小為 K的數(shù)組fiv1.K 。其中fivk 表示前i個(gè)物品、背包大小為v時(shí)，第k優(yōu)解的值?！癴iv是一個(gè)大小

47、為K的數(shù)組”這一句，熟悉C語言的同學(xué)可能比較好理解，或者也可以簡單地理解為在原來的 方程中加了一維。顯然fiv1.K 這K個(gè)數(shù)是由大到小排列的，所以我們把 它認(rèn)為是一個(gè)有序隊(duì)列。然后原方程就可以解釋為：fiv 這個(gè)有序隊(duì)列是由fi-1v 和 fi-1v-ci+wi這兩個(gè)有序隊(duì)列合并得到的。有序隊(duì)列fi-1v 即fi-1v1.K，fi-1v-ci+wi則理解為在 fi-1v-ci1.K的每個(gè)數(shù)上加上wi后得到的有序隊(duì)列。合并這兩個(gè)有序隊(duì)列并將結(jié)果（的前 K 項(xiàng)）儲(chǔ)存到fiv1.K中的復(fù)雜度是0（K）。最后的答案是fNVK。總的復(fù)雜度是O（NVK。為什么這個(gè)方法正確呢？實(shí)際上，一個(gè)正確的狀態(tài)轉(zhuǎn)移方

48、程的求解過程遍歷了所 有可用的策略，也就覆蓋了問題的所有方案。只不過由于是求最優(yōu)解，所以其它 在任何一個(gè)策略上達(dá)不到最優(yōu)的方案都被忽略了。如果把每個(gè)狀態(tài)表示成一個(gè)大小為K的數(shù)組，并在這個(gè)數(shù)組中有序的保存該狀態(tài)可取到的前 K個(gè)最優(yōu)值。那么, 對于任兩個(gè)狀態(tài)的max運(yùn)算等價(jià)于兩個(gè)由大到小的有序隊(duì)列的合并。另外還要注意題目對于“第 K優(yōu)解”的定義，將策略不同但權(quán)值相同的兩個(gè)方案 是看作同一個(gè)解還是不同的解。如果是前者，則維護(hù)有序隊(duì)列時(shí)要保證隊(duì)列里的 數(shù)沒有重復(fù)的。小結(jié)顯然，這里不可能窮盡背包類動(dòng)態(tài)規(guī)劃問題所有的問法。甚至還存在一類將背包類動(dòng)態(tài)規(guī)劃問題與其它領(lǐng)域（例如數(shù)論、圖論）結(jié)合起來的問題，在這篇

49、論背包 問題的專文中也不會(huì)論及。但只要深刻領(lǐng)會(huì)前述所有類別的背包問題的思路和狀 態(tài)轉(zhuǎn)移方程，遇到其它的變形問法，只要題目難度還屬于NOIP,應(yīng)該也不難想出算法。觸類旁通、舉一反三，應(yīng)該也是一個(gè) OIer應(yīng)有的品質(zhì)吧。首頁附：USAC中的背包問題USAC是USA Computing Olympiad的簡稱，它組織了很多面向全球的計(jì)算機(jī)競 賽活動(dòng)。USACCTrainng是一個(gè)很適合初學(xué)者的題庫，我認(rèn)為它的特色是題目質(zhì)量高，循 序漸進(jìn)，還配有不錯(cuò)的課文和題目分析。其中關(guān)于背包問題的那篇課文(TEXTKn apsack Problems)也值得一看。另外，USACOontest是USAC常年組織的面

50、向全球的競賽系列，在此也推薦NOIP 選手參加。我整理了 USACO Training中涉及背包問題的題目，應(yīng)該可以作為不錯(cuò)的習(xí)題。 其中標(biāo)加號(hào)的是我比較推薦的，標(biāo)嘆號(hào)的是我認(rèn)為對NOIP選手比較有挑戰(zhàn)性的。題目列表« Inflate (+)(基本 01 背包)* Stamps (+)(!)(對初學(xué)者有一定挑戰(zhàn)性)* Money* Nuggets* Subsets« Rockers (+)(另一類有趣的“二維”背包問題)* Milk4 (!)(很怪的背包問題問法，較難用純DP求解)題目簡解以下文字來自我所撰的USAC心得一文，該文的完整版本，包括我的程序， 可在DD的USA

51、C征程中找到。Inflate是加權(quán)01背包問題，也就是說：每種物品只有一件，只可以選擇放或者不放；而且每種物品有對應(yīng)的權(quán)值，目標(biāo)是使總權(quán)值最大或最小。它最樸素的 狀態(tài)轉(zhuǎn)移方程是：fki= maxfk-1i, fk-1i-vk+wk。fki表示前k件物品花費(fèi)代價(jià)i可以得到的最大權(quán)值。vk和wk分別是第k件物 品的花費(fèi)和權(quán)值?？梢钥吹剑琭k的求解過程就是使用第k件物品對fk-1 進(jìn)行更新的過程。那么事實(shí)上就不用使用二維數(shù)組，只需要定義fi，然后對于每件物品k，順序地檢查fi與fi-vk+wk的大小，如果后者更大，就對前者進(jìn)行更新。這是背包問題中典型的優(yōu)化方法。題目stamps中，每種物品的使用量沒

52、有直接限制，但使用物品的總量有限制。 求第一個(gè)不能用這有限個(gè)物品組成的背包的大小。(可以這樣等價(jià)地認(rèn)為)設(shè) fki 表示前k件物品組成大小為i的背包，最少需要物品的數(shù)量。則 fki= minfk-1i,fk-1i-j*sk+j，其中 j 是選擇使用第 k 件物品的數(shù)目，這個(gè)方程運(yùn)用時(shí)可以用和上面一樣的方法處理成一維的。求解時(shí)先設(shè)置一個(gè)粗糙的循環(huán)上限，即最大的物品乘最多物品數(shù)。Money是多重背包問題。也就是每個(gè)物品可以使用無限多次。要求解的是構(gòu)成一 種背包的不同方案總數(shù)?；旧暇褪前岩话愕亩嘀乇嘲姆匠讨械?min改成sum 就行了。Nuggets的模型也是多重背包。要求求解所給的物品不能恰好

53、放入的背包大小的 最大值(可能不存在)。只需要根據(jù)“若i、j互質(zhì)，則關(guān)于x、y的不定方程i*x+y*j=n 必有正整數(shù)解，其中n>i*j ”這一定理得出一個(gè)循環(huán)的上限。Subsets子集和問題相當(dāng)于物品大小是前 N個(gè)自然數(shù)時(shí)求大小為N*(N+1)/4的 01背包的方案數(shù)。Rockers可以利用求解背包問題的思想設(shè)計(jì)解法。我的狀態(tài)轉(zhuǎn)移方程如下：fijt=maxfijt-1 , fi-1jt , fi-1jt-timei+1 , fi-1j-1T+(t>=timei)。其中 fijt 表示前 i 首歌用 j 張完整的盤和一張錄了 t分鐘的盤可以放入的最多歌數(shù)，T是一張光盤的最大容量，

54、t>=timei是一個(gè)bool值轉(zhuǎn)換成int取值為0或1。但我后來發(fā)現(xiàn)我當(dāng)時(shí)設(shè)計(jì) 的狀態(tài)和方程效率有點(diǎn)低，如果換成這樣：fij=(a,b) 表示前i首歌中選了 j首需要用到a張完整的光盤以及一張錄了 b分鐘的光盤，會(huì)將時(shí)空復(fù)雜度都 大大降低。這種將狀態(tài)的值設(shè)為二維的方法值得注意。Milk4是這些類背包問題中難度最大的一道了。很多人無法做到將它用純DP方法求解，而是用迭代加深搜索枚舉使用的桶，將其轉(zhuǎn)換成多重背包問題再DF。由于USAC0的數(shù)據(jù)弱，迭代加深的深度很小，這樣也可以AC，但我們還是可以用純DP方法將它完美解決的。設(shè)fk為稱量出k單位牛奶需要的最少的桶數(shù)。 那么可以用類似多重背包的方法對 f數(shù)組反復(fù)