http://www.concretevitamin.com.cn/informatics/Pack/Index.html
背包問題九講
version 1.1 build 20071115
前言
目錄
第一講 01背包問題
第二講 完全背包問題
第三講 多重背包問題
第四講 混合三種背包問題
第五講 二維費(fèi)用的背包問題
第六講 分組的背包問題
第七講 有依賴的背包問題
第八講 泛化物品
第九講 背包問題問法的變化
附錄一：USACO中的背包問題
附錄二：背包問題的搜索解法
聯(lián)系方式
致謝
前言
本篇文章是我(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ī)劃模型。它既簡(jiǎn)單形象容易理解，又在某種程度上能夠揭示動(dòng)態(tài)規(guī)劃的本質(zhì)，故不少教材都把它作為動(dòng)態(tài)規(guī)劃部分的第一道例題，我也將它放在我的寫作計(jì)劃的第一部分。
讀本文最重要的是思考。因?yàn)槲业恼Z言和寫作方式向來不以易于理解為長(zhǎng)，思路也偶有跳躍的地方，后面更有需要大量思考才能理解的比較抽象的內(nèi)容。更重要的是：不大量思考，絕對(duì)不可能學(xué)好動(dòng)態(tài)規(guī)劃這一信息學(xué)奧賽中最精致的部分。
你現(xiàn)在看到的是本文的v1.1版，發(fā)布于2007年11月15日。我會(huì)長(zhǎng)期維護(hù)這份文本，把大家的意見和建議融入其中，也會(huì)不斷加入我在OI學(xué)習(xí)以及將來可能的ACM-ICPC的征程中得到的新的心得。但目前本文還沒有一個(gè)固定的發(fā)布頁面，想了解本文是否有更新版本發(fā)布，可以在OIBH論壇中以“背包問題九講”為關(guān)鍵字搜索貼子，每次比較重大的版本更新都會(huì)在這個(gè)論壇里發(fā)貼公布。也可以用“背包問題九講”為關(guān)鍵字在搜索引擎中搜索以得到最新版本。
目錄
第一講 01背包問題
這是最基本的背包問題，每個(gè)物品最多只能放一次。
P01: 01背包問題
題目
有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。
基本思路
這是最基礎(chǔ)的背包問題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。
用子問題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的。所以有必要將它詳細(xì)解釋一下：“將前i件物品放入容量為v的背包中”這個(gè)子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”，價(jià)值為f[i-1][v]；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時(shí)能獲得的最大價(jià)值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價(jià)值w[i]。
優(yōu)化空間復(fù)雜度
以上方法的時(shí)間和空間復(fù)雜度均為O(VN)，其中時(shí)間復(fù)雜度應(yīng)該已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以優(yōu)化到O。
先考慮上面講的基本思路如何實(shí)現(xiàn)，肯定是有一個(gè)主循環(huán)i=1..N，每次算出來二維數(shù)組f[i][0..V]的所有值。那么，如果只用一個(gè)數(shù)組f[0..V]，能不能保證第i次循環(huán)結(jié)束后f[v]中表示的就是我們定義的狀態(tài)f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]兩個(gè)子問題遞推而來，能否保證在推f[i][v]時(shí)（也即在第i次主循環(huán)中推f[v]時(shí)）能夠得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事實(shí)上，這要求在每次主循環(huán)中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時(shí)f[v-c[i]]保存的是狀態(tài)f[i-1][v-c[i]]的值。偽代碼如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當(dāng)于我們的轉(zhuǎn)移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因?yàn)楝F(xiàn)在的f[v-c[i]]就相當(dāng)于原來的f[i-1][v-c[i]]。如果將v的循環(huán)順序從上面的逆序改成順序的話，那么則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另一個(gè)重要的背包問題P02最簡(jiǎn)捷的解決方案，故學(xué)習(xí)只用一維數(shù)組解01背包問題是十分必要的。
事實(shí)上，使用一維數(shù)組解01背包的程序在后面會(huì)被多次用到，所以這里抽象出一個(gè)處理一件01背包中的物品過程，以后的代碼中直接調(diào)用不加說明。
過程ZeroOnePack，表示處理一件01背包中的物品，兩個(gè)參數(shù)cost、weight分別表明這件物品的費(fèi)用和價(jià)值。
procedure ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
注意這個(gè)過程里的處理與前面給出的偽代碼有所不同。前面的示例程序?qū)懗蓈=V..0是為了在程序中體現(xiàn)每個(gè)狀態(tài)都按照方程求解了，避免不必要的思維復(fù)雜度。而這里既然已經(jīng)抽象成看作黑箱的過程了，就可以加入優(yōu)化。費(fèi)用為cost的物品不會(huì)影響狀態(tài)f[0..cost-1]，這是顯然的。
有了這個(gè)過程以后，01背包問題的偽代碼就可以這樣寫：
for i=1..N
ZeroOnePack(c[i],w[i]);
初始化的細(xì)節(jié)問題
我們看到的求最優(yōu)解的背包問題題目中，事實(shí)上有兩種不太相同的問法。有的題目要求“恰好裝滿背包”時(shí)的最優(yōu)解，有的題目則并沒有要求必須把背包裝滿。一種區(qū)別這兩種問法的實(shí)現(xiàn)方法是在初始化的時(shí)候有所不同。
如果是第一種問法，要求恰好裝滿背包，那么在初始化時(shí)除了f[0]為0其它f[1..V]均設(shè)為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優(yōu)解。
如果并沒有要求必須把背包裝滿，而是只希望價(jià)格盡量大，初始化時(shí)應(yīng)該將f[0..V]全部設(shè)為0。
為什么呢？可以這樣理解：初始化的f數(shù)組事實(shí)上就是在沒有任何物品可以放入背包時(shí)的合法狀態(tài)。如果要求背包恰好裝滿，那么此時(shí)只有容量為0的背包可能被價(jià)值為0的nothing“恰好裝滿”，其它容量的背包均沒有合法的解，屬于未定義的狀態(tài)，它們的值就都應(yīng)該是-∞了。如果背包并非必須被裝滿，那么任何容量的背包都有一個(gè)合法解“什么都不裝”，這個(gè)解的價(jià)值為0，所以初始時(shí)狀態(tài)的值也就全部為0了。
這個(gè)小技巧完全可以推廣到其它類型的背包問題，后面也就不再對(duì)進(jìn)行狀態(tài)轉(zhuǎn)移之前的初始化進(jìn)行講解。
一個(gè)常數(shù)優(yōu)化
前面的偽代碼中有 for v=V..1，可以將這個(gè)循環(huán)的下限進(jìn)行改進(jìn)。
由于只需要最后f[v]的值，倒推前一個(gè)物品，其實(shí)只要知道f[v-w[n]]即可。以此類推，對(duì)以第j個(gè)背包，其實(shí)只需要知道到f[v-sum{w[j..n]}]即可，即代碼中的
for i=1..N
for v=V..0
可以改成
for i=1..n
bound=max{V-sum{w[i..n]},c[i]}
for v=V..bound
這對(duì)于V比較大時(shí)是有用的。
小結(jié)
01背包問題是最基本的背包問題，它包含了背包問題中設(shè)計(jì)狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉(zhuǎn)換成01背包問題求解。故一定要仔細(xì)體會(huì)上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及最后怎樣優(yōu)化的空間復(fù)雜度。
第二講 完全背包問題
第二個(gè)基本的背包問題模型，每種物品可以放無限多次。
P02: 完全背包問題
題目
有N種物品和一個(gè)容量為V的背包，每種物品都有無限件可用。第i種物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。
基本思路
這個(gè)問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01背包時(shí)的思路，令f[i][v]表示前i種物品恰放入一個(gè)容量為v的背包的最大權(quán)值。仍然可以按照每種物品不同的策略寫出狀態(tài)轉(zhuǎn)移方程，像這樣：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
這跟01背包問題一樣有O(VN)個(gè)狀態(tài)需要求解，但求解每個(gè)狀態(tài)的時(shí)間已經(jīng)不是常數(shù)了，求解狀態(tài)f[i][v]的時(shí)間是O(v/c[i])，總的復(fù)雜度可以認(rèn)為是O(V*Σ(V/c[i]))，是比較大的。
將01背包問題的基本思路加以改進(jìn)，得到了這樣一個(gè)清晰的方法。這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問題。但我們還是試圖改進(jìn)這個(gè)復(fù)雜度。
一個(gè)簡(jiǎn)單有效的優(yōu)化
完全背包問題有一個(gè)很簡(jiǎn)單有效的優(yōu)化，是這樣的：若兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j]，則將物品j去掉，不用考慮。這個(gè)優(yōu)化的正確性顯然：任何情況下都可將價(jià)值小費(fèi)用高得j換成物美價(jià)廉的i，得到至少不會(huì)更差的方案。對(duì)于隨機(jī)生成的數(shù)據(jù)，這個(gè)方法往往會(huì)大大減少物品的件數(shù)，從而加快速度。然而這個(gè)并不能改善最壞情況的復(fù)雜度，因?yàn)橛锌赡芴貏e設(shè)計(jì)的數(shù)據(jù)可以一件物品也去不掉。
這個(gè)優(yōu)化可以簡(jiǎn)單的O(N^2)地實(shí)現(xiàn)，一般都可以承受。另外，針對(duì)背包問題而言，比較不錯(cuò)的一種方法是：首先將費(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背包問題來解。最簡(jiǎn)單的想法是，考慮到第i種物品最多選V/c[i]件，于是可以把第i種物品轉(zhuǎn)化為V/c[i]件費(fèi)用及價(jià)值均不變的物品，然后求解這個(gè)01背包問題。這樣完全沒有改進(jìn)基本思路的時(shí)間復(fù)雜度，但這畢竟給了我們將完全背包問題轉(zhuǎn)化為01背包問題的思路：將一種物品拆成多件物品。
更高效的轉(zhuǎn)化方法是：把第i種物品拆成費(fèi)用為c[i]*2^k、價(jià)值為w[i]*2^k的若干件物品，其中k滿足c[i]*2^k<=V。這是二進(jìn)制的思想，因?yàn)椴还茏顑?yōu)策略選幾件第i種物品，總可以表示成若干個(gè)2^k件物品的和。這樣把每種物品拆成O(log V/c[i])件物品，是一個(gè)很大的改進(jìn)。
但我們有更優(yōu)的O(VN)的算法。
O(VN)的算法
這個(gè)算法使用一維數(shù)組，先看偽代碼：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-cost]+weight}
你會(huì)發(fā)現(xiàn)，這個(gè)偽代碼與P01的偽代碼只有v的循環(huán)次序不同而已。為什么這樣一改就可行呢？首先想想為什么P01中要按照v=V..0的逆序來循環(huán)。這是因?yàn)橐ＷC第i次循環(huán)中的狀態(tài)f[i][v]是由狀態(tài)f[i-1][v-c[i]]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時(shí)，依據(jù)的是一個(gè)絕無已經(jīng)選入第i件物品的子結(jié)果f[i-1][v-c[i]]。而現(xiàn)在完全背包的特點(diǎn)恰是每種物品可選無限件，所以在考慮“加選一件第i種物品”這種策略時(shí)，卻正需要一個(gè)可能已選入第i種物品的子結(jié)果f[i][v-c[i]]，所以就可以并且必須采用v=0..V的順序循環(huán)。這就是這個(gè)簡(jiǎn)單的程序?yàn)楹纬闪⒌牡览怼?/p>
值得一提的是，上面的偽代碼中兩層for循環(huán)的次序可以顛倒。這個(gè)結(jié)論有可能會(huì)帶來算法時(shí)間常數(shù)上的優(yōu)化。
這個(gè)算法也可以以另外的思路得出。例如，將基本思路中求解f[i][v-c[i]]的狀態(tài)轉(zhuǎn)移方程顯式地寫出來，代入原方程中，會(huì)發(fā)現(xiàn)該方程可以等價(jià)地變形成這種形式：
f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}
將這個(gè)方程用一維數(shù)組實(shí)現(xiàn)，便得到了上面的偽代碼。
最后抽象出處理一件完全背包類物品的過程偽代碼：
procedure CompletePack(cost,weight)
for v=cost..V
f[v]=max{f[v],f[v-c[i]]+w[i]}
總結(jié)
完全背包問題也是一個(gè)相當(dāng)基礎(chǔ)的背包問題，它有兩個(gè)狀態(tài)轉(zhuǎn)移方程，分別在“基本思路”以及“O(VN)的算法“的小節(jié)中給出。希望你能夠?qū)@兩個(gè)狀態(tài)轉(zhuǎn)移方程都仔細(xì)地體會(huì)，不僅記住，也要弄明白它們是怎么得出來的，最好能夠自己想一種得到這些方程的方法。事實(shí)上，對(duì)每一道動(dòng)態(tài)規(guī)劃題目都思考其方程的意義以及如何得來，是加深對(duì)動(dòng)態(tài)規(guī)劃的理解、提高動(dòng)態(tài)規(guī)劃功力的好方法。
第三講 多重背包問題
每種物品有一個(gè)固定的次數(shù)上限。
P03: 多重背包問題
題目
有N種物品和一個(gè)容量為V的背包。第i種物品最多有n[i]件可用，每件費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。
基本算法
這題目和完全背包問題很類似。基本的方程只需將完全背包問題的方程略微一改即可，因?yàn)閷?duì)于第i種物品有n[i]+1種策略：取0件，取1件……取n[i]件。令f[i][v]表示前i種物品恰放入一個(gè)容量為v的背包的最大權(quán)值，則有狀態(tài)轉(zhuǎn)移方程：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
復(fù)雜度是O(V*Σn[i])。
轉(zhuǎn)化為01背包問題
另一種好想好寫的基本方法是轉(zhuǎn)化為01背包求解：把第i種物品換成n[i]件01背包中的物品，則得到了物品數(shù)為Σn[i]的01背包問題，直接求解，復(fù)雜度仍然是O(V*Σn[i])。
但是我們期望將它轉(zhuǎn)化為01背包問題之后能夠像完全背包一樣降低復(fù)雜度。仍然考慮二進(jìn)制的思想，我們考慮把第i種物品換成若干件物品，使得原問題中第i種物品可取的每種策略——取0..n[i]件——均能等價(jià)于取若干件代換以后的物品。另外，取超過n[i]件的策略必不能出現(xiàn)。
方法是：將第i種物品分成若干件物品，其中每件物品有一個(gè)系數(shù)，這件物品的費(fèi)用和價(jià)值均是原來的費(fèi)用和價(jià)值乘以這個(gè)系數(shù)。使這些系數(shù)分別為1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數(shù)。例如，如果n[i]為13，就將這種物品分成系數(shù)分別為1,2,4,6的四件物品。
分成的這幾件物品的系數(shù)和為n[i]，表明不可能取多于n[i]件的第i種物品。另外這種方法也能保證對(duì)于0..n[i]間的每一個(gè)整數(shù)，均可以用若干個(gè)系數(shù)的和表示，這個(gè)證明可以分0..2^k-1和2^k..n[i]兩段來分別討論得出，并不難，希望你自己思考嘗試一下。
這樣就將第i種物品分成了O(log n[i])種物品，將原問題轉(zhuǎn)化為了復(fù)雜度為<math>O(V*Σlog n[i])的01背包問題，是很大的改進(jìn)。
下面給出O(log amount)時(shí)間處理一件多重背包中物品的過程，其中amount表示物品的數(shù)量：
procedure MultiplePack(cost,weight,amount)
if cost*amount>=V
CompletePack(cost,weight)
return
integer k=1
while k<amount
ZeroOnePack(k*cost,k*weight)
amount=amount-k
k=k*2
ZeroOnePack(amount*cost,amount*weight)
希望你仔細(xì)體會(huì)這個(gè)偽代碼，如果不太理解的話，不妨翻譯成程序代碼以后，單步執(zhí)行幾次，或者頭腦加紙筆模擬一下，也許就會(huì)慢慢理解了。
O(VN)的算法
多重背包問題同樣有O(VN)的算法。這個(gè)算法基于基本算法的狀態(tài)轉(zhuǎn)移方程，但應(yīng)用單調(diào)隊(duì)列的方法使每個(gè)狀態(tài)的值可以以均攤O(1)的時(shí)間求解。由于用單調(diào)隊(duì)列優(yōu)化的DP已超出了NOIP的范圍，故本文不再展開講解。我最初了解到這個(gè)方法是在樓天成的“男人八題”幻燈片上。
小結(jié)
這里我們看到了將一個(gè)算法的復(fù)雜度由O(V*Σn[i])改進(jìn)到O(V*Σlog n[i])的過程，還知道了存在應(yīng)用超出NOIP范圍的知識(shí)的O(VN)算法。希望你特別注意“拆分物品”的思想和方法，自己證明一下它的正確性，并將完整的程序代碼寫出來。