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最簡捷的解決方案，故學(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ù)雜度。
P02: 完全背包問題
題目
有N種物品和一個(gè)容量為V的背包，每種物品都有無限件可用。第i種物品的容量是c[i]，價(jià)值是w[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]，f[i-1][v] }（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è)簡單有效的優(yōu)化
完全背包問題有一個(gè)很簡單有效的優(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)化可以簡單的O(N^2)地實(shí)現(xiàn)，一般都可以承受。另外，針對(duì)背包問題而言，比較不錯(cuò)的一種方法是：首先將容量大于V的物品去掉，然后使用類似計(jì)數(shù)排序的做法，計(jì)算出容量相同的物品中價(jià)值最高的是哪個(gè)（只要保留價(jià)值大的就行了，和上面的篩選一樣），可以O(shè)(V+N)地完成這個(gè)優(yōu)化。這個(gè)不太重要的過程就不給出偽代碼了，希望你能獨(dú)立思考寫出偽代碼或程序。
轉(zhuǎn)化為01背包問題求解
既然01背包問題是最基本的背包問題，那么我們可以考慮把完全背包問題轉(zhuǎn)化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/c[i]件，于是可以把第i種物品轉(zhuǎn)化為V/c[i]件容量及價(jià)值均不變的物品，然后求解這個(gè)01背包問題。這樣完全沒有改進(jìn)基本思路的時(shí)間復(fù)雜度，但這畢竟給了我們將完全背包問題轉(zhuǎn)化為01背包問題的思路：將一種物品拆成多件物品。
更高效的轉(zhuǎn)化方法是：把第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è)簡單的程序?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=c[i]..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ī)劃功力的好方法。
P03: 多重背包問題
題目
有N種物品和一個(gè)容量為V的背包。第i種物品最多有n[i]件可用，每件容量是c[i]，價(jià)值是w[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]，f[i][v] }（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ù)，這件物品的容量和價(jià)值均是原來的容量和價(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(log2n[i])種物品，將原問題轉(zhuǎn)化為了復(fù)雜度為O(V*Σlog2n[i])的01背包問題，是很大的改進(jìn)。
下面給出O(log amount)時(shí)間處理一件多重背包中物品的過程，其中amount表示物品的數(shù)量：
procedure MultiplePack(cost,weight,amount) if cost*amount>=V //如果i種物品足夠多，那么就相當(dāng)與無限多了 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)算法。希望你特別注意“拆分物品”的思想和方法，自己證明一下它的正確性，并將完整的程序代碼寫出來。
P04: 混合三種背包問題
問題
如果將P01、P02、P03混合起來。也就是說，有的物品只可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數(shù)有一個(gè)上限（多重背包）。應(yīng)該怎么求解呢？
01背包與完全背包的混合
考慮到在P01和P02中給出的偽代碼只有一處不同，故如果只有兩類物品：一類物品只能取一次，另一類物品可以取無限次，那么只需在對(duì)每個(gè)物品應(yīng)用轉(zhuǎn)移方程時(shí)，根據(jù)物品的類別選用順序或逆序的循環(huán)即可，復(fù)雜度是O(VN)。偽代碼如下：
for i=1..N if 第i件物品屬于01背包 for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]}; else if 第i件物品屬于完全背包 for v=0..V f[v]=max{f[v],f[v-c[i]]+w[i]};再加上多重背包
如果再加上有的物品最多可以取有限次，那么原則上也可以給出O(VN)的解法：遇到多重背包類型的物品用單調(diào)隊(duì)列解即可。但如果不考慮超過NOIP范圍的算法的話，用P03中將每個(gè)這類物品分成O(log n[i])個(gè)01背包的物品的方法也已經(jīng)很優(yōu)了。
當(dāng)然，更清晰的寫法是調(diào)用我們前面給出的三個(gè)相關(guān)過程。
for i=1..N if 第i件物品屬于01背包 ZeroOnePack(c[i],w[i]) else if 第i件物品屬于完全背包 CompletePack(c[i],w[i]) else if 第i件物品屬于多重背包 MultiplePack(c[i],w[i],n[i])在最初寫出這三個(gè)過程的時(shí)候，可能完全沒有想到它們會(huì)在這里混合應(yīng)用。我想這體現(xiàn)了編程中抽象的威力。如果你一直就是以這種“抽象出過程”的方式寫每一類背包問題的，也非常清楚它們的實(shí)現(xiàn)中細(xì)微的不同，那么在遇到混合三種背包問題的題目時(shí)，一定能很快想到上面簡潔的解法，對(duì)嗎？
小結(jié)
有人說，困難的題目都是由簡單的題目疊加而來的。這句話是否公理暫且存之不論，但它在本講中已經(jīng)得到了充分的體現(xiàn)。本來01背包、完全背包、多重背包都不是什么難題，但將它們簡單地組合起來以后就得到了這樣一道一定能嚇倒不少人的題目。但只要基礎(chǔ)扎實(shí)，領(lǐng)會(huì)三種基本背包問題的思想，就可以做到把困難的題目拆分成簡單的題目來解決。
文章來源:
http://www.cnblogs.com/kuangbin/archive/2011/11/16/2250560.html