P01: 01背包問題 ZeroOnePack
題目
有N件物品和一個容量為V的背包卧须。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。
基本思路
這是最基礎的背包問題送漠，特點是：每種物品僅有一件，可以選擇放或不放由蘑。
用子問題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值闽寡。則其狀態(tài)轉移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的尼酿。所以有必要將它詳細解釋一下：“將前i件物品放入容量為v的背包中”這個子問題爷狈，若只考慮第i件物品的策略（放或不放），那么就可以轉化為一個只牽扯前i-1件物品的問題裳擎。如果不放第i件物品涎永，那么問題就轉化為“前i-1件物品放入容量為v的背包中”，價值為f[i-1][v]鹿响；如果放第i件物品羡微，那么問題就轉化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]抢野。
優(yōu)化空間復雜度
以上方法的時間和空間復雜度均為O(VN)，其中時間復雜度應該已經不能再優(yōu)化了各墨，但空間復雜度卻可以優(yōu)化到O指孤。
先考慮上面講的基本思路如何實現(xiàn)，肯定是有一個主循環(huán)i=1..N贬堵，每次算出來二維數組f[i][0..V]的所有值恃轩。那么，如果只用一個數組f[0..V]黎做，能不能保證第i次循環(huán)結束后f[v]中表示的就是我們定義的狀態(tài)f[i][v]呢叉跛？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環(huán)中推f[v]時）能夠得到f[i-1][v]和f[i-1][v-c[i]]的值呢蒸殿？事實上筷厘，這要求在每次主循環(huán)中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]保存的是狀態(tài)f[i-1][v-c[i]]的值宏所。偽代碼如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當于我們的轉移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}
酥艳，因為現(xiàn)在的f[v-c[i]]就相當于原來的f[i-1][v-c[i]]。如果將v的循環(huán)順序從上面的逆序改成順序的話爬骤，那么則成了f[i][v]由f[i][v-c[i]]推知充石，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案霞玄，故學習只用一維數組解01背包問題是十分必要的骤铃。
事實上拉岁，使用一維數組解01背包的程序在后面會被多次用到，所以這里抽象出一個處理一件01背包中的物品過程惰爬，以后的代碼中直接調用不加說明喊暖。
過程ZeroOnePack，表示處理一件01背包中的物品补鼻，兩個參數cost哄啄、weight分別表明這件物品的費用和價值。
procedure ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
注意這個過程里的處理與前面給出的偽代碼有所不同风范。前面的示例程序寫成v=V..0是為了在程序中體現(xiàn)每個狀態(tài)都按照方程求解了咨跌，避免不必要的思維復雜度。而這里既然已經抽象成看作黑箱的過程了硼婿，就可以加入優(yōu)化锌半。費用為cost的物品不會影響狀態(tài)f[0..cost-1]，這是顯然的寇漫。
有了這個過程以后刊殉，01背包問題的偽代碼就可以這樣寫：
for i=1..N
ZeroOnePack(c[i],w[i]);
初始化的細節(jié)問題
我們看到的求最優(yōu)解的背包問題題目中，事實上有兩種不太相同的問法州胳。有的題目要求“恰好裝滿背包”時的最優(yōu)解记焊，有的題目則并沒有要求必須把背包裝滿。一種區(qū)別這兩種問法的實現(xiàn)方法是在初始化的時候有所不同栓撞。
如果是第一種問法遍膜，要求恰好裝滿背包，那么在初始化時除了f[0]為0其它f[1..V]均設為-∞瓤湘，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優(yōu)解瓢颅。
如果并沒有要求必須把背包裝滿，而是只希望價格盡量大弛说，初始化時應該將f[0..V]全部設為0挽懦。
為什么呢？可以這樣理解：初始化的f數組事實上就是在沒有任何物品可以放入背包時的合法狀態(tài)木人。如果要求背包恰好裝滿信柿，那么此時只有容量為0的背包可能被價值為0的nothing“恰好裝滿”，其它容量的背包均沒有合法的解醒第，屬于未定義的狀態(tài)角塑，它們的值就都應該是-∞了。如果背包并非必須被裝滿淘讥，那么任何容量的背包都有一個合法解“什么都不裝”圃伶，這個解的價值為0，所以初始時狀態(tài)的值也就全部為0了。
這個小技巧完全可以推廣到其它類型的背包問題窒朋，后面也就不再對進行狀態(tài)轉移之前的初始化進行講解搀罢。
一個常數優(yōu)化
前面的偽代碼中有 for v=V..1，可以將這個循環(huán)的下限進行改進侥猩。
由于只需要最后f[v]的值榔至，倒推前一個物品，其實只要知道f[v-w[n]]即可欺劳。以此類推唧取，對以第j個背包，其實只需要知道到f[v-sum{w[j..n]}]即可划提，即代碼中的
for i=1..N
for v=V..0
可以改成
for i=1..n
bound=max{V-sum{w[i..n]},c[i]}
for v=V..bound
這對于V比較大時是有用的枫弟。
小結
01背包問題是最基本的背包問題，它包含了背包問題中設計狀態(tài)鹏往、方程的最基本思想淡诗，另外，別的類型的背包問題往往也可以轉換成01背包問題求解伊履。故一定要仔細體會上面基本思路的得出方法韩容，狀態(tài)轉移方程的意義，以及最后怎樣優(yōu)化的空間復雜度唐瀑。
原帖：origin: http://love-oriented.com/pack/P01.html
