背包九講

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

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

3、vc[i]]再加上通過放入第i件物品獲得的價值w[i]。優(yōu)化空間復雜度優(yōu)化空間復雜度以上方法的時間和空間復雜度均為O(NV)，其中時間復雜度基本已經(jīng)不能再優(yōu)化了，但空間復雜度卻可以優(yōu)化到O(V)。先考慮上面講的基本思路如何實現(xiàn)，肯定是有一個主循環(huán)i=1..N，每次算出來二維數(shù)組f[i][0..V]的所有值。那么，如果只用一個數(shù)組f[0..V]，能不能保證第i次循環(huán)結束后f[v]中表示的就是我們定義的狀態(tài)f[i][v]呢？f[i][v]是

4、由f[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]其中的f[v]=ma

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