背包九講

1、P01:P01:0101背包問題背包問題題目題目有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]=maxf[i1][v]f[i1][vc[i]]w[i]這個(gè)方程非

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

3、vc[i]]再加上通過放入第i件物品獲得的價(jià)值w[i]。優(yōu)化空間復(fù)雜度優(yōu)化空間復(fù)雜度以上方法的時(shí)間和空間復(fù)雜度均為O(NV)，其中時(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]是

4、由f[i1][v]和f[i1][vc[i]]兩個(gè)子問題遞推而來，能否保證在推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]=ma

5、xf[v]f[vc[i]]一句恰就相當(dāng)于我們的轉(zhuǎn)移方程f[i][v]=maxf[i1][v]f[i1][vc[i]]，因?yàn)楝F(xiàn)在的f[vc[i]]就相當(dāng)于原來的這個(gè)小技巧完全可以推廣到其它類型的背包問題，后面也就不再對(duì)進(jìn)行狀態(tài)轉(zhuǎn)移之前的初始化進(jìn)行講解。小結(jié)小結(jié)01背包問題是最基本的背包問題，它包含了背包問題中設(shè)計(jì)狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉(zhuǎn)換成01背包問題求解。故一定要仔細(xì)體會(huì)上面基本思路的得出方法，狀態(tài)轉(zhuǎn)