有關背包

1、P01:P01:0101背包問題背包問題題目題目有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大?；舅悸坊舅悸愤@是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態(tài)轉(zhuǎn)移方程便是：f[i][v]=maxf[i1][v]f[i1][vc[i]]w[i]這個方程非

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

3、vc[i]]再加上通過放入第i件物品獲得的價值w[i]。優(yōu)化空間復雜度優(yōu)化空間復雜度以上方法的時間和空間復雜度均為O(VN)，其中時間復雜度應該已經(jīng)不能再優(yōu)化了，但空間復雜度卻可以優(yōu)化到O。先考慮上面講的基本思路如何實現(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[

4、i1][v]和f[i1][vc[i]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環(huán)中推f[v]時）能夠得到f[i1][v]和f[i1][vc[i]]的值呢？事實上，這要求在每次主循環(huán)中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[vc[i]]保存的是狀態(tài)f[i1][vc[i]]的值。偽代碼如下：fi=1..Nfv=V..0f[v]=maxf[v]f[vc[i]]w[i]這個小技巧完全可以推廣到其

5、它類型的背包問題，后面也就不再對進行狀態(tài)轉(zhuǎn)移之前的初始化進行講解。一個常數(shù)優(yōu)化一個常數(shù)優(yōu)化前面的偽代碼中有fv=V..1，可以將這個循環(huán)的下限進行改進。由于只需要最后f[v]的值，倒推前一個物品，其實只要知道f[vw[n]]即可。以此類推，對以第j個背包，其實只需要知道到f[vsumw[j..n]]即可，即代碼中的fi=1..Nfv=V..0可以改成fi=1..nbound=maxVsumw[i..n]c[i]fv=V..bound這對

6、于V比較大時是有用的。小結(jié)小結(jié)01背包問題是最基本的背包問題，它包含了背包問題中設計狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉(zhuǎn)換成01背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及最后怎樣優(yōu)化的空間復雜度。P02:P02:完全背包問題完全背包問題題目題目有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的