【學界】0-1背包問題的動態規劃演算法

【學界】0-1背包問題的動態規劃演算法

來自專欄『運籌OR帷幄』大數據人工智慧時代的運籌學

文章作者: @Bat特白 (原文鏈接:0-1背包問題的動態規劃演算法)

責任編輯: @文雨之

歡迎原鏈接轉發,轉載請私信 @留德華叫獸 獲取信息,盜版必究。

敬請關注和擴散本專欄及同名公眾號,會邀請全球知名學者發布運籌學、人工智慧中優化理論等相關乾貨、知乎Live及行業動態:『運籌OR帷幄』大數據人工智慧時代的運籌學

1、首先得知道什麼是0-1背包問題(knapsack problem)

賊,夜入豪宅,可偷之物甚多,而負重能力有限,偷哪些才更加不枉此行?

抽象的話,就是:

給定一組多個(n)物品,每種物品都有自己的重量(w_i)和價值(v_i),在限定的總重量/總容量(C)內,選擇其中若干個(也即每種物品可以選0個或1個),設計選擇方案使得物品的總價值最高。

更加抽象的話:

給定正整數{(w_i,v_i)}_{1leq ileq n}、給定正整數C,求解0-1規劃問題:

max sum_{i=1}^{n}{x_iv_i} , s.t. sum_{i=1}^{n}{x_iw_i}leq Cx_iin{0,1}

示例應用:處理器能力有限時間受限,任務很多,如何選擇使得總效用最大?

數值例子:如下圖。

2、0-1背包問題的定性

對於一般性的0-1背包,

貪婪演算法無法得到最優解。

反例,不多解釋——

事實上它可能想多差有多差(以 v/w 作為「貪婪」的標準,也不多解釋了)——

確定性問題版本的背包問題是NP的,

w_i=v_i,求x_iin{0,1}使得sum_{i=1}^{n}{x_iw_i}= C 」是Karp的21個NPC問題之一(實際上Karp的表述是現在所稱的子集和(subset sum)問題)。

3、0-1背包問題的遞推關係

定義子問題 mathbf{	ext{P(i, W)}} 為:在前 i 個物品中挑選總重量不超過 W 的物品,每種物品至多只能挑選1個,使得總價值最大;這時的最優值記作 m(i,W) ,其中 1leq ileq n1leq Wleq C

考慮第 i 個物品,無外乎兩種可能:選,或者不選。

  • 不選的話,背包的容量不變,改變為問題 mathbf{{P(i-1, W)}}
  • 選的話,背包的容量變小,改變為問題 mathbf{{P(i-1, W-w_i)}}

最優方案就是比較這兩種方案,哪個會更好些:

m(i,W)=max{m(i-1,W),m(i-1,W-w_i)+v_i}

得到

[m(i,W)=left{ egin{array}{*{55}{l}} 0 & 	ext{if } i=	ext{0} \ 0 & 	ext{if } W=	ext{0} \ m(i-1,W) & 	ext{if }{w_i>W} \ max left{ m(i-1,W),{{v}_{i}}+m(i-1,W-{{w}_{i}}) 
ight} & 	ext{otherwise} \ end{array} 
ight.]

4、「填二維表」的動態規劃方法

演算法就很自然了:

之前的例子填表的結果是——

(藍色格子表示本行值發生變化的格子)

然後發生 m(i,W)=m(i-1,W-w_i)+v_i 時才會有「取第 i 件物品」發生。

所以從表格右下角「往回看」如果是「垂直下降」就是發生了 m(i,W)=m(i-1,W) ,而只有「走斜線」才是「取了」物品。

這個演算法的複雜度就很容易算了——每一個格子都要填寫數字,所以時間複雜度和空間複雜度都是Omega(nC) 。當" C>2^n "時(就不嚴謹地使用漸近分析的語言了),複雜度是 Omega(n2^n)

5、所謂「填一維表」的動態規劃方法

其實呢,上面那個二維表,也可以用一行來存儲啊!對不啦?

所以,根本的區別在於思想,而不是具體存儲方式。

那麼這個演算法的思想又是什麼呢?——其實就是:

  • 每行都有些數值相同的哦,所以
  • 只記錄每行里那些不同的數值就好了啊。

例如上面的表格中,只記錄藍色的部分,

格式是(i,W,m(i,W))(為了方便閱讀,再貼一次圖):

(0,0,0)

(1,0,0)(1,1,1)

(2,0,0)(2,1,1)(2,2,6)(2,3,7)

(3,0,0)(3,1,1)(3,2,6)(3,3,7)(3,5,18)(3,6,19)(3,7,24)(3,8,25)

……(不寫了,累)

你會說,這也沒省什麼地方啊?!

的確,對於這個例子來說是這樣的——要不然數值太大我畫不下。

你假設每個 w_i 都擴大1000倍,那樣的話,表格也擴大到1000倍,填表時間也增加到1000倍,然而藍色的格子還是那麼多

好了,繼續,下面有三個問題:

  1. m(i,W)geq m(i-1,W)m(i,W)geq m(i,W-1) ;(這比較顯然)
  2. 什麼時候會發生「 m(i,W)> m(i,W-1) 」的情況?
  3. 什麼時候會發生「 m(i,W)> m(i-1,W) 」的情況?

下面來看問題2,一定是發生了「容量擴大後有個新的東西可以放下了」!

所以固定 i ,讓 W 變化, m(i,W) 一定是「階梯狀」的:

  • 有的 w 使得 m(i,w)> m(i,w-1)
  • 有的 w 使得 m(i,w)= m(i,w-1)

例如,前面例子中 m(1,w) 如下圖所示:

看下m(2,W)=max{m(1,W),m(1,W-w_2)+v_2}m(1,W-w_2)+v_2m(1,W)右移w_2上移v_2

所以 m(2,W)w_2=2,v_2=6 )就是下述兩條「階梯」

在max意義下的「疊加」。

比較m(1,W)m(2,W) 的「轉折點」:

m(1,W) 的是 S^1={(1,0,0),(1,1,1)}m(2,W) 的是 S^2={(2,0,0),(2,1,1),(2,2,6),(2,3,7)}

於是:

  • 對於每一個 im(i ,W) 最多只有 2^i 個「轉折點」——因為 i 個物品,最多只有 2^i個「選」、「不選」的組合;
  • m(2,W)m(1,W-w_2)+v_2 那部分的所有可能的「轉折點」就是由 m(1,W) 的每個轉折點 (1,w,v) 變為 (2,w+w_2,v+v_2);(「可能」這個詞後面再解釋)
  • 推而廣之, m(i+1,W)m(i,W-w_{i+1})+v_{i+1} 那部分的所有可能的「轉折點」就是由 m(i,W) 的每個轉折點 (i,w,v) 變為 (i+1,w+w_{i+1},v+v_{i+1})

設置S^0={(0,0,0)},則由S^i得到S^{i+1}的所有可能的「轉折點」為{(i+1,w+w_{i+1},v+v_{i+1})}:(i,w,v)in S^i

例如m(3,W)

例如m(4,W)w_4=6,v_4=22

這時有些問題:

  1. 超過 C=11 的部分可以不用考慮;
  2. 綠色的圓形里有些「轉折點」被湮沒了——這就是之前說的「可能」的意思。

來看哦, S^3={(3,0,0),(3,1,1),(3,2,6),(3,3,7),(3,5,18),(3,6,19),(3,7,24),(3,8,25)}

於是 S^4 的所有可能應該是

{(4,0,0),(4,1,1),(4,2,6),(4,3,7),(4,5,18),(4,6,19),(4,7,24),(4,8,25)}

cup

{(4,0+6,0+22),(4,1+6,1+22),(4,2+6,6+22),(4,3+6,7+22),

(4,5+6,18+22),(4,6+6,19+22),(4,7+6,24+22),(4,8+6,25+22)}

Ok,首先刪除掉第二分量大於 C=11 的(上圖紅框里)(稱作第一類拋棄),得到

{(4,0,0),(4,1,1),(4,2,6),(4,3,7),(4,5,18),(4,6,19),(4,7,24),(4,8,25)}cup

{(4,6,22),(4,7,23),(4,8,28),(4,9,29),(4,11,40)}

然後按第二分量遞增排序,得到:

按道理說,對於階梯函數來說,如果第二分量是遞增的,那麼第三分量也應該是遞增的。但是上圖中紅框里不是哦——事實上它們是「被湮沒」的「轉折點」(上圖的黃色圓形)。

所以哦,棄掉他們(稱作第二類拋棄),得到 {(4,0,0),(4,1,1),(4,2,6),(4,3,7),(4,5,18),(4,6,22),(4,7,24),(4,8,28),(4,9,29),(4,11,40)},就是下圖 。

而最終結果就是S^n 的最後一項的第三個分量

S^i得到S^{i+1} 的過程是(例如):

S^3={(3,0,0),(3,1,1),(3,2,6),(3,3,7),(3,5,18),(3,6,19),(3,7,24),(3,8,25)}

已經按照第二分量遞增排序好,

之後先寫成

{(4,0,0),(4,1,1),(4,2,6),(4,3,7),(4,5,18),(4,6,19),(4,7,24),(4,8,25)}

然後對第一個三元組,

刪除當前位置之後被「湮沒」的

對第二個三元組,一定是插入當前位置之後,並被立即「湮沒」,

不斷這樣進行下去,並注意第一類拋棄即可得到 S^4

S^0={(0,0,0)},則可以得到(由於分行了,就不在乎三元組的第一分量了):

然後所謂「一維」存儲,其實就是把它「存儲成了」一維,例如使用兩個一維數組和一個start數組做「分割」:

然後就是如何得到方案——

S^5 的最後一個是不是與 S^4 的最後一個相同,相同的話就直接看 S^4

S^4 的最後一個與 S^3 的最後一個不同,所以一定拿了物品4,然後看 S^3 第二分量不超過5(= C-w_4 )的最後一個,是 (5,18)

(5,18)S^2 的最後一個不同,所以一定拿了物品3;

……然後類推。

最後是分析複雜度:

路線是計算 S^i 的元素個數,然後對 i 求和,就得到了所有「藍色格子」的數量。

然後,

  • 首先,由於 S^{i+1} 在不考慮兩類拋棄的情況下(最差情況就是不發生這兩類拋棄),元素個數恰好等於 S^i 元素數的兩倍;也可以這樣來看——對於每一個 im(i,W) 最多只有 2^i 個「轉折點」;
  • S^i 得到 S^{i+1} 時, S^i 中各組的第二分量、第三分量一定彼此不同,那麼每個 (i,w,m(i,w)) 中的 w 的取值範圍是 0leq wleq C ,第三分量的取值範圍是 0simsum_{k=1}^{i}{v_i} 。所以這樣的三元組最多有 min{C+1,sum_{k=1}^{i}{v_k}+1} 個。

i=1sim n 求和,得到

  • 「藍色格子」數目leq (1+2^1+2^2+...+2^n)=O(2^n) ;
  • 「藍色格子」數目leq n(C+1)=O(nC)
  • 「藍色格子」數目leq sum_{i=1}^{n}{sum_{k=1}^{i}({v_i}+1)}leq sum_{i=1}^{n}{sum_{k=1}^{n}({v_k}+1)}=n+nsum_{k=1}^{n}{v_k}=O(nsum_{k=1}^{n}{v_k})

而由 S^i 產生 S^{i+1} 的計算過程主要就是產生一個新的對、插入、刪除(拋棄),所以這個過程的計算量是和 S^i 元素數成正比的。

所以得到,無論空間複雜度還是時間複雜度,都是 O(min{2^n,nC,nsum_{k=1}^{n}{v_k}}) 的。

即使 C>2^n ,這時的演算法複雜度也控制在 O(2^n) 之內。


如果你是運籌學/人工智慧碩博或在讀,請在下圖的公眾號後台留言:「加微信群」。系統會自動辨認你的關鍵字,並提示您進一步的加群要求和步驟,邀請您進全球運籌或AI學者群(群內學界、業界大佬雲集)。

同時我們有:【運籌學|優化愛好者】【供應鏈|物流】【人工智慧】【數據科學|分析】千人QQ群,想入群的小夥伴可以關注下方公眾號點擊「加入社區」按鈕,獲得入群傳送門。

學術界|工業界招聘、徵稿等信息免費發布,請見下圖:


推薦閱讀:

運籌學、人工智慧、數據科學尋學術合作,承接工業界諮詢,歡迎訪問海德堡大學組合優化實驗室、圖像處理中心
【供應鏈】運籌學與供應鏈管理
運籌學S01E05——動態規劃
OPL建模語言從入門到放棄(二)
【學界】機器學習、數據科學 如何進階成為大神?

TAG:演算法 | 運籌學 | 動態規劃 |