acm背包問題九講

1、背包問題九講背包問題九講目錄第一講01背包問題第二講完全背包問題第三講多重背包問題第四講混合三種背包問題第五講二維費(fèi)用的背包問題第六講分組的背包問題第七講有依賴的背包問題第八講泛化物品第九講背包問題問法的變化附錄一：USACO中的背包問題附錄二：背包問題的搜索解法P01:01背包問題背包問題題目題目有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大?；舅悸坊舅悸愤@是最基

2、礎(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è)方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的。所以有必要將它詳細(xì)解釋一下：“將前i件物品放入容量為v的背包中”這個(gè)子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化

3、為一個(gè)只牽扯前i1件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i1件物品放入容量為v的背包中”，價(jià)值為f[i1][v]；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i1件物品放入剩下的容量為vc[i]的背包中”，此時(shí)能獲得的最大價(jià)值就是f[i1][vc[i]]再加上通過放入第i件物品獲得的價(jià)值w[i]。優(yōu)化空間復(fù)雜度優(yōu)化空間復(fù)雜度以上方法的時(shí)間和空間復(fù)雜度均為O(VN)，其中時(shí)間復(fù)雜度應(yīng)該已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以優(yōu)化到O

4、。先考慮上面講的基本思路如何實(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]中表為什么呢？可以這樣理解：初始化的f數(shù)組事實(shí)上就是在沒有任何物品可以放入背包時(shí)的合法狀態(tài)。如果要求背包恰好裝滿，那么此時(shí)只有容量為0的背包可能被價(jià)值為0的nothing“恰好裝滿”，其它容量的背包均沒有合法的解，屬于未定義的狀態(tài)，它們的值就都應(yīng)該是∞了

5、。如果背包并非必須被裝滿，那么任何容量的背包都有一個(gè)合法解“什么都不裝”，這個(gè)解的價(jià)值為0，所以初始時(shí)狀態(tài)的值也就全部為0了。這個(gè)小技巧完全可以推廣到其它類型的背包問題，后面也就不再對(duì)進(jìn)行狀態(tài)轉(zhuǎn)移之前的初始化進(jìn)行講解。一個(gè)常數(shù)優(yōu)化一個(gè)常數(shù)優(yōu)化前面的偽代碼中有fv=V..1，可以將這個(gè)循環(huán)的下限進(jìn)行改進(jìn)。由于只需要最后f[v]的值，倒推前一個(gè)物品，其實(shí)只要知道f[vw[n]]即可。以此類推，對(duì)以第j個(gè)背包，其實(shí)只需要知道到f[vsumw[

6、j..n]]即可，即代碼中的fi=1..Nfv=V..0可以改成fi=1..nbound=maxVsumw[i..n]c[i]fv=V..bound這對(duì)于V比較大時(shí)是有用的。小結(jié)小結(jié)01背包問題是最基本的背包問題，它包含了背包問題中設(shè)計(jì)狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉(zhuǎn)換成01背包問題求解。故一定要仔細(xì)體會(huì)上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及最后怎樣優(yōu)化的空間復(fù)雜度。P02:完全背包問題完全背包問題