背包-問(wèn)題九講

1、背包九講背包九講P01:P01:0101背包問(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

2、[i]這個(gè)方程非常重要，基本上所有跟背包相關(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à)值

3、就是f[i1][vc[i]]再加上通過(guò)放入第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。先考慮上面講的基本思路如何實(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

4、][v]是由f[i1][v]和f[i1][vc[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數(shù)組事實(shí)上就是在沒(méi)有任何物品可以放入背包時(shí)的合法狀態(tài)。如果要求背包恰好裝滿，那么此時(shí)只有容量為0的背包可能被價(jià)值為0的nothing“恰好裝滿”，

5、其它容量的背包均沒(méi)有合法的解，屬于未定義的狀態(tài)，它們的值就都應(yīng)該是∞了。如果背包并非必須被裝滿，那么任何容量的背包都有一個(gè)合法解“什么都不裝”，這個(gè)解的價(jià)值為0，所以初始時(shí)狀態(tài)的值也就全部為0了。這個(gè)小技巧完全可以推廣到其它類型的背包問(wèn)題，后面也就不再對(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[

6、n]]即可。以此類推，對(duì)以第j個(gè)背包，其實(shí)只需要知道到f[vsumw[j..n]]即可，即代碼中的fi=1..Nfv=V..0可以改成fi=1..nbound=maxVsumw[i..n]c[i]fv=V..bound這對(duì)于V比較大時(shí)是有用的。小結(jié)小結(jié)01背包問(wèn)題是最基本的背包問(wèn)題，它包含了背包問(wèn)題中設(shè)計(jì)狀態(tài)、方程的最基本思想，另外，別的類型的背包問(wèn)題往往也可以轉(zhuǎn)換成01背包問(wèn)題求解。故一定要仔細(xì)體會(huì)上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程