背包問(wèn)題九講

1、P01:01背包問(wèn)題背包問(wèn)題題目：有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大?；舅悸愤@是最基礎(chǔ)的背包問(wèn)題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。用子問(wèn)題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：f[i][v]=maxf[i1][v]f[i1][vc[i]]w[i]這個(gè)方程非常重要，基本上所有跟背

2、包相關(guān)的問(wèn)題的方程都是由它衍生出來(lái)的。所以有必要將它詳細(xì)解釋一下：“將前i件物品放入容量為v的背包中”這個(gè)子問(wèn)題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i1件物品的問(wèn)題。如果不放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i1件物品放入容量為v的背包中”，價(jià)值為f[i1][v]；如果放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i1件物品放入剩下的容量為vc[i]的背包中”，此時(shí)能獲得的最大價(jià)值就是f[i1][vc[i]]再加上通過(guò)

3、放入第i件物品獲得的價(jià)值w[i]。優(yōu)化空間復(fù)雜度以上方法的時(shí)間和空間復(fù)雜度均為O(NV)，其中時(shí)間復(fù)雜度基本已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以?xún)?yōu)化到O(V)。先考慮上面講的基本思路如何實(shí)現(xiàn)，肯定是有一個(gè)主循環(huán)i=1..N，每次算出來(lái)二維數(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[i1][v]和f[i1][vc

4、[i]]兩個(gè)子問(wèn)題遞推而來(lái)，能否保證在推f[i][v]時(shí)（也即在第i次主循環(huán)中推f[v]時(shí)）能夠得到f[i1][v]和f[i1][vc[i]]的值呢？事實(shí)上，這要求在每次主循環(huán)中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時(shí)f[vc[i]]保存的是狀態(tài)f[i1][vc[i]]的值。偽代碼如下：fi=1..Nfv=V..0f[v]=maxf[v]f[vc[i]]w[i]其中的f[v]=maxf[v]f[vc[i]]一句恰就相

5、當(dāng)于我們的轉(zhuǎn)移方程f[i][v]=maxf[i1][v]f[i1][vc[i]]，因?yàn)楝F(xiàn)在的f[vc[i]]就相當(dāng)于原來(lái)的f[i1][vc[i]]。如果將v的循環(huán)順序從上面的逆序改成順序的話，那么則成了f[i][v]由f[i][vc[i]]推知，與本題意不符，但它卻是另一個(gè)重要的背包問(wèn)題P02最簡(jiǎn)捷的解決方案，故學(xué)習(xí)只用一維數(shù)組解01背包問(wèn)題是十分必要的。事實(shí)上，使用一維數(shù)組解01背包的程序在后面會(huì)被多次用到，所以這里抽象出一個(gè)處理一件

6、01背包中的物品過(guò)程，以后的代碼中直接調(diào)用不加說(shuō)明。過(guò)程ZeroOnePack，表示處理一件01背包中的物品，兩個(gè)參數(shù)cost、weight分別表明這件物品的費(fèi)用和價(jià)值。procedureZeroOnePack(costweight)fv=V..costf[v]=maxf[v]f[vcost]weight注意這個(gè)過(guò)程里的處理與前面給出的偽代碼有所不同。前面的示例程序?qū)懗蓈=V..0是為了在程序中體現(xiàn)每個(gè)狀態(tài)都按照方程求解了，避免不必要的

7、思維復(fù)雜度。而這里既然已經(jīng)抽象成看作黑箱的過(guò)程了，就可以加入優(yōu)化。費(fèi)用為cost的物品不會(huì)影響狀態(tài)f[0..cost1]，這是顯然的。有了這個(gè)過(guò)程以后，01背包問(wèn)題的偽代碼就可以這樣寫(xiě)：fi=1..NZeroOnePack(c[i]w[i])初始化的細(xì)節(jié)問(wèn)題我們看到的求最優(yōu)解的背包問(wèn)題題目中，事實(shí)上有兩種不太相同的問(wèn)法。有的題目要求“恰好裝滿(mǎn)背包”時(shí)的最優(yōu)解，有的題目則并沒(méi)有要求必須把背包裝滿(mǎn)。一種區(qū)別這兩種問(wèn)法的實(shí)現(xiàn)方法是在初始化的時(shí)

8、候有所不同。如果是第一種問(wèn)法，要求恰好裝滿(mǎn)背包，那么在初始化時(shí)除了f[0]為0其它f[1..V]均設(shè)為∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿(mǎn)背包的最優(yōu)解。如果并沒(méi)有要求必須把背包裝滿(mǎn)，而是只希望價(jià)格盡量大，初始化時(shí)應(yīng)該將f[0..V]全部設(shè)為0。為什么呢？可以這樣理解：初始化的f數(shù)組事實(shí)上就是在沒(méi)有任何物品可以放入背包時(shí)的合法狀態(tài)。如果要求慮“加選一件第i種物品”這種策略時(shí)，卻正需要一個(gè)可能已選入第i種物品的子結(jié)果f[i][

9、vc[i]]，所以就可以并且必須采用v=0..V的順序循環(huán)。這就是這個(gè)簡(jiǎn)單的程序?yàn)楹纬闪⒌牡览?。這個(gè)算法也可以以另外的思路得出。例如，基本思路中的狀態(tài)轉(zhuǎn)移方程可以等價(jià)地變形成這種形式：f[i][v]=maxf[i1][v]f[i][vc[i]]w[i]將這個(gè)方程用一維數(shù)組實(shí)現(xiàn)，便得到了上面的偽代碼。最后抽象出處理一件完全背包類(lèi)物品的過(guò)程偽代碼，以后會(huì)用到：procedureCompletePack(costweight)fv=cost.

10、.Vf[v]=maxf[v]f[vc[i]]w[i]總結(jié)完全背包問(wèn)題也是一個(gè)相當(dāng)基礎(chǔ)的背包問(wèn)題，它有兩個(gè)狀態(tài)轉(zhuǎn)移方程，分別在“基本思路”以及“O(VN)的算法“的小節(jié)中給出。希望你能夠?qū)@兩個(gè)狀態(tài)轉(zhuǎn)移方程都仔細(xì)地體會(huì)，不僅記住，也要弄明白它們是怎么得出來(lái)的，最好能夠自己想一種得到這些方程的方法。事實(shí)上，對(duì)每一道動(dòng)態(tài)規(guī)劃題目都思考其方程的意義以及如何得來(lái)，是加深對(duì)動(dòng)態(tài)規(guī)劃的理解、提高動(dòng)態(tài)規(guī)劃功力的好方法。P03:多重背包問(wèn)題多重背包問(wèn)題題

11、目有N種物品和一個(gè)容量為V的背包。第i種物品最多有n[i]件可用，每件費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。基本算法這題目和完全背包問(wèn)題很類(lèi)似。基本的方程只需將完全背包問(wèn)題的方程略微一改即可，因?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]=maxf

12、[i1][vkc[i]]kw[i]|00的最大整數(shù)。例如，如果n[i]為13，就將這種物品分成系數(shù)分別為1246的四件物品。分成的這幾件物品的系數(shù)和為n[i]，表明不可能取多于n[i]件的第i種物品。另外這種方法也能保證對(duì)于0..n[i]間的每一個(gè)整數(shù)，均可以用若干個(gè)系數(shù)的和表示，這個(gè)證明可以分0..2^k1和2^k..n[i]兩段來(lái)分別討論得出，并不難，希望你自己思考嘗試一下。這樣就將第i種物品分成了O(logn[i])種物品，將原問(wèn)