//詳解來自《背包問題九講》崔添翼(Tianyi Cui) 2011-09-28
1 01 背包問題
1.1 題目有 N 件物品和一個容量為 V 的背包。放入第 i件物品耗費(fèi)的費(fèi)用是 Ci1，得到的價(jià)值是 Wi。求解將哪些物品裝入背包可使價(jià)值總和最大。1.2 基本思路這是最基礎(chǔ)的背包問題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)：即 F [ i, v ] 表示前 i 件物品恰放入一個容量為 v 的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：F [ i, v ] = max {F [i ? 1, v ], F [i ? 1, v ? Ci ] + Wi }這個方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的。所以有必要將它詳細(xì)解釋一下：“將前 i 件物品放入容量為 v 的背包中”這個子問題，若只考慮第 i 件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個只和前 i ? 1 件物品相關(guān)的問題。如果不放第 i 件物品，那么問題就轉(zhuǎn)化為“前 i ? 1 件物品放入容量為 v 的背包中”，價(jià)值為 F [i ? 1, v ]；如果放第 i 件物品，那么問題就轉(zhuǎn)化為“前 i ? 1 件物品放入剩下的容量為 v ? Ci 的背包中”，此時能獲得的最大價(jià)值就是 F [i ? 1, v ? Ci ] 再加上通過放入第 i 件物品獲得的價(jià)值 Wi。偽代碼如下：F [0, 0..V ] ← 0for i ← 1 to Nfor v ← 0 to Ci ? 1F [i, v ] ← F [i ? 1, v ]for v ← Ci to VF [i, v ] ← max {F [i ? 1, v ], F [i ? 1, v ? Ci ] + Wi }1.3 優(yōu)化空間復(fù)雜度以上方法的時間和空間復(fù)雜度均為 O (V N )，其中時間復(fù)雜度應(yīng)該已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以優(yōu)化到 O (V )。先考慮上面講的基本思路如何實(shí)現(xiàn)，肯定是有一個主循環(huán) i ← 1 . . . N，每次算出來二維數(shù)組 F [i, 0 . . . V ] 的所有值。那么，如果只用一個數(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 ? Ci ] 兩個子問題遞推而來，能否保證在推 F [i, v ] 時（也即在第 i 次主循環(huán)中推 F [v ] 時）能夠取用 F [i ? 1, v ] 和 F [i ? 1, v ? Ci ] 的值呢？事實(shí)上，這要求在每次主循環(huán)中我們以 v ← V . . . 0 的遞減順序計(jì)算 F [v ]，這樣才能保證計(jì)算 F [v ] 時 F [v ? Ci ] 保存的是狀態(tài) F [i ? 1, v ? Ci ] 的值。偽代碼如下：1也即占用背包的空間容量，后文統(tǒng)一稱之為“費(fèi)用 (cost)”3F [0 ..V ] ← 0for i ← 1 to Nfor v ← V to CiF [ v ] ← max {F [v ], F [v ? Ci ] + Wi }其中的 F [v ] ← max {F [v ], F [v ? Ci ] + Wi } 一句，恰就對應(yīng)于我們原來的轉(zhuǎn)移方程，因?yàn)楝F(xiàn)在的 F [v ? Ci ] 就相當(dāng)于原來的 F [i ? 1, v ? Ci ]。如果將 v 的循環(huán)順序從上面的逆序改成順序的話，那么則成了 F [i, v ] 由 F [i, v ? Ci ] 推導(dǎo)得到，與本題意不符。事實(shí)上，使用一維數(shù)組解 01 背包的程序在后面會被多次用到，所以這里抽象出一個處理一件 01 背包中的物品過程，以后的代碼中直接調(diào)用不加說明。def ZeroOnePack(F, C, W)for v ← V to CF [v ] ← max (F [v ], f [v ? C ] + W )有了這個過程以后， 01 背包問題的偽代碼就可以這樣寫：F [0..V ] ← 0for i ← 1 to NZeroOnePack(F, Ci, Wi)1.4 初始化的細(xì)節(jié)問題我們看到的求最優(yōu)解的背包問題題目中，事實(shí)上有兩種不太相同的問法。有的題目要求“恰好裝滿背包”時的最優(yōu)解，有的題目則并沒有要求必須把背包裝滿。一種區(qū)別這兩種問法的實(shí)現(xiàn)方法是在初始化的時候有所不同。如果是第一種問法，要求恰好裝滿背包，那么在初始化時除了 F [0] 為 0，其它F [1..V ] 均設(shè)為 ?∞，這樣就可以保證最終得到的 F [V ] 是一種恰好裝滿背包的最優(yōu)解。如果并沒有要求必須把背包裝滿，而是只希望價(jià)格盡量大，初始化時應(yīng)該將 F [0..V ]全部設(shè)為 0。這是為什么呢？可以這樣理解：初始化的 F 數(shù)組事實(shí)上就是在沒有任何物品可以放入背包時的合法狀態(tài)。如果要求背包恰好裝滿，那么此時只有容量為 0 的背包可以在什么也不裝且價(jià)值為 0 的情況下被“恰好裝滿”，其它容量的背包均沒有合法的解，屬于未定義的狀態(tài)，應(yīng)該被賦值為 -∞ 了。如果背包并非必須被裝滿，那么任何容量的背包都有一個合法解“什么都不裝”，這個解的價(jià)值為 0，所以初始時狀態(tài)的值也就全部為 0了。這個小技巧完全可以推廣到其它類型的背包問題，后面不再對進(jìn)行狀態(tài)轉(zhuǎn)移之前的初始化進(jìn)行講解。1.5 一個常數(shù)優(yōu)化上面?zhèn)未a中的for i ← 1 to Nfor v ← V to Ci4中第二重循環(huán)的下限可以改進(jìn)。它可以被優(yōu)化為for i ← 1 to Nfor v ← V to max ( V ? Σ Ni Wi,Ci )這個優(yōu)化之所以成立的原因請讀者自己思考。（提示：使用二維的轉(zhuǎn)移方程思考較易。）1.6 小結(jié)01 背包問題是最基本的背包問題，它包含了背包問題中設(shè)計(jì)狀態(tài)、方程的最基本思想。另外，別的類型的背包問題往往也可以轉(zhuǎn)換成 01 背包問題求解。故一定要仔細(xì)體會上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及空間復(fù)雜度怎樣被優(yōu)化。
//HDU 2602#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int h[1005];int v[1005];int main (){ int t,n,m,l; int f[1005]; scanf("%d",&t); while (t--) { scanf("%d%d",&n,&m); for (int i = 1; i <= n; i++) scanf("%d",&v[i]); for (int i = 1; i <= n; i++) scanf("%d",&h[i]); memset(f,0,sizeof(f)); for (int i = 1; i <= n; i++) {// for(int j = m; j >= h[i]; j--)//j是放入物品i之后的容量 f[j] = max(f[j],f[j-h[i]]+v[i]); } PRintf("%d/n",f[m]); } return 0;}
新聞熱點(diǎn)
疑難解答
