背包問題匯總

1、部分背包書P74（貪心，按斤計算，求平均價值）最基本的背包問題：（回溯，給重量，看能否裝滿）；P01:01背包問題題目有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。基本思路這是最基礎(chǔ)的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其

2、狀態(tài)轉(zhuǎn)移方程便是：f[i][v]=maxf[i1][v]f[i1][vc[i]]w[i]。這個方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的。所以有必要將它詳細(xì)解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個只牽扯前i1件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i1件物品放入容量為v的背包中”；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i1件物

3、品放入剩下的容量為vc[i]的背包中”，此時能獲得的最大價值就是f[i1][vc[i]]再加上通過放入第i件物品獲得的價值w[i]。注意f[i][v]有意義當(dāng)且僅當(dāng)存在一個前i件物品的子集，其費用總和為v。所以按照這個方程遞推完畢后，最終的答案并不一定是f[N][V]，而是f[N][0..V]的最大值。如果將狀態(tài)的定義中的“恰”字去掉，在轉(zhuǎn)移方程中就要再加入一項f[i][v1]，這樣就可以保證f[N][V]就是最后的答案。至于為什么這樣

4、就可以，由你自己來體會了。優(yōu)化空間復(fù)雜度以上方法的時間和空間復(fù)雜度均為O(NV)，其中時間復(fù)雜度基本已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以優(yōu)化到O(V)。先考慮上面講的基本思路如何實現(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[i1][v]和f[i1][vc[i]]

5、兩個子問題遞推而來，能否保證在推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]=maxf[v]f[vc[i]]一句恰就相當(dāng)于我們

6、的轉(zhuǎn)移方程f[i][v]=maxf[i1][v]f[i1][vc[i]]，因為現(xiàn)在的f[vc[i]]就相當(dāng)于原來的f[i1][vc[i]]。如果將v的循環(huán)順序從上面的逆序改成順序的話，那么則成了f[i][v]由f[i][vc[i]]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學(xué)習(xí)只用一維數(shù)組解01背包問題是十分必要的。總結(jié)01背包問題是最基本的背包問題，它包含了背包問題中設(shè)計狀態(tài)、方程的最基本思想，另外，別

7、的類型的背包問題往往也可以轉(zhuǎn)換成01背包問題求解。故一定要仔細(xì)體會上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及最后怎樣優(yōu)化的空間復(fù)雜度。完全背包問題也是一個相當(dāng)基礎(chǔ)的背包問題，它有兩個狀態(tài)轉(zhuǎn)移方程，分別在“基本思路”以及“O(VN)的算法“的小節(jié)中給出。希望你能夠?qū)@兩個狀態(tài)轉(zhuǎn)移方程都仔細(xì)地體會，不僅記住，也要弄明白它們是怎么得出來的，最好能夠自己想一種得到這些方程的方法。事實上，對每一道動態(tài)規(guī)劃題目都思考其方程的意義以及如何得來，

8、是加深對動態(tài)規(guī)劃的理解、提高動態(tài)規(guī)劃功力的好方法。P03:多重背包問題題目有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大?；舅惴ㄟ@題目和完全背包問題很類似?；镜姆匠讨恍鑼⑼耆嘲鼏栴}的方程略微一改即可，因為對于第i種物品有n[i]1種策略：取0件，取1件……取n[i]件。令f[i][v]表示前i種物品恰放入

9、一個容量為v的背包的最大權(quán)值，則：f[i][v]=maxf[i1][vkc[i]]kw[i]|00的最大整數(shù)。例如，如果n[i]為13，就將這種物品分成系數(shù)分別為1246的四件物品。分成的這幾件物品的系數(shù)和為n[i]，表明不可能取多于n[i]件的第i種物品。另外這種方法也能保證對于0..n[i]間的每一個整數(shù)，均可以用若干個系數(shù)的和表示，這個證明可以分0..2^k1和2^k..n[i]兩段來分別討論得出，并不難，希望你自己思考嘗試一下。

10、這樣就將第i種物品分成了O(logn[i])種物品，將原問題轉(zhuǎn)化為了復(fù)雜度為O(V∑logn[i])的01背包問題，是很大的改進(jìn)。O(VN)的算法多重背包問題同樣有O(VN)的算法。這個算法基于基本算法的狀態(tài)轉(zhuǎn)移方程，但應(yīng)用單調(diào)隊列的方法使每個狀態(tài)的值可以以均攤O(1)的時間求解。由于用單調(diào)隊列優(yōu)化的DP已超出了NOIP的范圍，故本文不再展開講解。我最初了解到這個方法是在樓天成的“男人八題”幻燈片上。小結(jié)這里我們看到了將一個算法的復(fù)雜度