01背包問題 dynamic programming

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

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末群凶,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子哄辣,更是在濱河造成了極大的恐慌请梢,老刑警劉巖,帶你破解...
    沈念sama閱讀 217,084評論 6 503
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件柔滔,死亡現(xiàn)場離奇詭異溢陪,居然都是意外死亡萍虽,警方通過查閱死者的電腦和手機睛廊,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,623評論 3 392
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來杉编,“玉大人超全,你說我怎么就攤上這事〉寺” “怎么了嘶朱?”我有些...
    開封第一講書人閱讀 163,450評論 0 353
  • 文/不壞的土叔 我叫張陵,是天一觀的道長光酣。 經常有香客問我疏遏,道長,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,322評論 1 293
  • 正文 為了忘掉前任财异,我火速辦了婚禮倘零,結果婚禮上,老公的妹妹穿的比我還像新娘戳寸。我一直安慰自己呈驶,他們只是感情好,可當我...
    茶點故事閱讀 67,370評論 6 390
  • 文/花漫 我一把揭開白布疫鹊。 她就那樣靜靜地躺著,像睡著了一般。 火紅的嫁衣襯著肌膚如雪量淌。 梳的紋絲不亂的頭發(fā)上逸邦,一...
    開封第一講書人閱讀 51,274評論 1 300
  • 那天,我揣著相機與錄音锈拨,去河邊找鬼砌庄。 笑死,一個胖子當著我的面吹牛奕枢,可吹牛的內容都是我干的娄昆。 我是一名探鬼主播,決...
    沈念sama閱讀 40,126評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼缝彬,長吁一口氣:“原來是場噩夢啊……” “哼萌焰!你這毒婦竟也來了?” 一聲冷哼從身側響起谷浅,我...
    開封第一講書人閱讀 38,980評論 0 275
  • 序言:老撾萬榮一對情侶失蹤扒俯,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后一疯,有當地人在樹林里發(fā)現(xiàn)了一具尸體撼玄,經...
    沈念sama閱讀 45,414評論 1 313
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 37,599評論 3 334
  • 正文 我和宋清朗相戀三年墩邀,在試婚紗的時候發(fā)現(xiàn)自己被綠了掌猛。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 39,773評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡眉睹,死狀恐怖荔茬,靈堂內的尸體忽然破棺而出,到底是詐尸還是另有隱情竹海,我是刑警寧澤慕蔚,帶...
    沈念sama閱讀 35,470評論 5 344
  • 正文 年R本政府宣布,位于F島的核電站斋配,受9級特大地震影響孔飒,放射性物質發(fā)生泄漏灌闺。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 41,080評論 3 327
  • 文/蒙蒙 一坏瞄、第九天 我趴在偏房一處隱蔽的房頂上張望菩鲜。 院中可真熱鬧,春花似錦惦积、人聲如沸接校。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,713評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽蛛勉。三九已至,卻和暖如春睦柴,著一層夾襖步出監(jiān)牢的瞬間诽凌,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,852評論 1 269
  • 我被黑心中介騙來泰國打工坦敌, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留侣诵,地道東北人。 一個月前我還...
    沈念sama閱讀 47,865評論 2 370
  • 正文 我出身青樓狱窘,卻偏偏與公主長得像杜顺,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子蘸炸,可洞房花燭夜當晚...
    茶點故事閱讀 44,689評論 2 354

推薦閱讀更多精彩內容