背包九講完整版_背包九講

《背包九講完整版_背包九講》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、背包九講P01:01背包問題題目有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fè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ì)解釋一下：“將

2、前i件物品放入容量為v的背包中”這個(gè)子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時(shí)能獲得的最大價(jià)值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價(jià)值w[i]。注意f[i][v]有意義當(dāng)且僅當(dāng)存在一個(gè)前i件物品的子集，其費(fèi)用總和為v。所以按照這個(gè)方程遞推完畢后，最終的答案并不一定是f[N][V]，而是f[N][0..V]的最大

3、值。如果將狀態(tài)的定義中的“恰”字去掉，在轉(zhuǎn)移方程中就要再加入一項(xiàng)f[i][v-1]，這樣就可以保證f[N][V]就是最后的答案。至于為什么這樣就可以，由你自己來體會(huì)了。優(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ù)組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]

4、和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]]的值。偽代碼如下：fori=1..Nforv=V..0f[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

5、],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背包問題是十分必要的?？偨Y(jié)01背包問題是最基本的背包問題，它包含了背包問題中設(shè)計(jì)狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉(zhuǎn)換成01背包問題求解。故一定要仔細(xì)體會(huì)上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及最后怎樣優(yōu)化的空間復(fù)雜度。P02:完

6、全背包問題題目有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

7、*c[i]]+k*w[i]

8、0<=k*c[i]<=v}。這跟01背包問題一樣有O(N*V)個(gè)狀態(tài)需要求解，但求解每個(gè)狀態(tài)的時(shí)間則不是常數(shù)了，求解狀態(tài)f[i][v]的時(shí)間是O(v/c[i])，總的復(fù)雜度是超過O(VN)的。將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)化的正確性顯然：任何情況

9、下都可將價(jià)值小費(fèi)用高得j換成物美價(jià)廉的i，得到至少不會(huì)更差的方案。對(duì)于隨機(jī)生成的