【學界】0-1背包問題的動態規劃演算法
來自專欄『運籌OR帷幄』大數據人工智慧時代的運籌學
文章作者: @Bat特白 (原文鏈接:0-1背包問題的動態規劃演算法)
責任編輯: @文雨之 歡迎原鏈接轉發,轉載請私信 @留德華叫獸 獲取信息,盜版必究。敬請關注和擴散本專欄及同名公眾號,會邀請全球知名學者發布運籌學、人工智慧中優化理論等相關乾貨、知乎Live及行業動態:『運籌OR帷幄』大數據人工智慧時代的運籌學
1、首先得知道什麼是0-1背包問題(knapsack problem)
賊,夜入豪宅,可偷之物甚多,而負重能力有限,偷哪些才更加不枉此行?
抽象的話,就是:
給定一組多個()物品,每種物品都有自己的重量()和價值(),在限定的總重量/總容量()內,選擇其中若干個(也即每種物品可以選0個或1個),設計選擇方案使得物品的總價值最高。
更加抽象的話:
給定正整數、給定正整數,求解0-1規劃問題:
, s.t. , 。
示例應用:處理器能力有限時間受限,任務很多,如何選擇使得總效用最大?
數值例子:如下圖。
2、0-1背包問題的定性
對於一般性的0-1背包,
貪婪演算法無法得到最優解。
反例,不多解釋——
事實上它可能想多差有多差(以 作為「貪婪」的標準,也不多解釋了)——
確定性問題版本的背包問題是NP的,
「,求使得 」是Karp的21個NPC問題之一(實際上Karp的表述是現在所稱的子集和(subset sum)問題)。
3、0-1背包問題的遞推關係
定義子問題 為:在前 個物品中挑選總重量不超過 的物品,每種物品至多只能挑選1個,使得總價值最大;這時的最優值記作 ,其中 , 。
考慮第 個物品,無外乎兩種可能:選,或者不選。
- 不選的話,背包的容量不變,改變為問題 ;
- 選的話,背包的容量變小,改變為問題 。
最優方案就是比較這兩種方案,哪個會更好些:
。
得到
。
4、「填二維表」的動態規劃方法
演算法就很自然了:
之前的例子填表的結果是——
(藍色格子表示本行值發生變化的格子)
然後發生 時才會有「取第 件物品」發生。
所以從表格右下角「往回看」如果是「垂直下降」就是發生了 ,而只有「走斜線」才是「取了」物品。
這個演算法的複雜度就很容易算了——每一個格子都要填寫數字,所以時間複雜度和空間複雜度都是 。當" "時(就不嚴謹地使用漸近分析的語言了),複雜度是 。
5、所謂「填一維表」的動態規劃方法
其實呢,上面那個二維表,也可以用一行來存儲啊!對不啦?
所以,根本的區別在於思想,而不是具體存儲方式。
那麼這個演算法的思想又是什麼呢?——其實就是:
- 每行都有些數值相同的哦,所以
- 只記錄每行里那些不同的數值就好了啊。
例如上面的表格中,只記錄藍色的部分,
格式是(為了方便閱讀,再貼一次圖):
、
、 、
、 、 、 、
、 、 、 、 、 、 、 、
……(不寫了,累)
你會說,這也沒省什麼地方啊?!
的確,對於這個例子來說是這樣的——要不然數值太大我畫不下。
你假設每個 都擴大1000倍,那樣的話,表格也擴大到1000倍,填表時間也增加到1000倍,然而藍色的格子還是那麼多。
好了,繼續,下面有三個問題:
- , ;(這比較顯然)
- 什麼時候會發生「 」的情況?
- 什麼時候會發生「 」的情況?
下面來看問題2,一定是發生了「容量擴大後有個新的東西可以放下了」!
所以固定 ,讓 變化, 一定是「階梯狀」的:
- 有的 使得 ;
- 有的 使得 。
例如,前面例子中 如下圖所示:
看下,是右移上移 。
所以 ( )就是下述兩條「階梯」
在max意義下的「疊加」。
比較和 的「轉折點」:
的是 ; 的是 。
於是:
- 對於每一個 , 最多只有 個「轉折點」——因為 個物品,最多只有 個「選」、「不選」的組合;
- 中 那部分的所有可能的「轉折點」就是由 的每個轉折點 變為 ;(「可能」這個詞後面再解釋)
- 推而廣之, 中 那部分的所有可能的「轉折點」就是由 的每個轉折點 變為 。
設置,則由得到的所有可能的「轉折點」為 。
例如 :
例如 , :
這時有些問題:
- 超過 的部分可以不用考慮;
- 綠色的圓形里有些「轉折點」被湮沒了——這就是之前說的「可能」的意思。
來看哦, 。
於是 的所有可能應該是
Ok,首先刪除掉第二分量大於 的(上圖紅框里)(稱作第一類拋棄),得到
。
然後按第二分量遞增排序,得到:
按道理說,對於階梯函數來說,如果第二分量是遞增的,那麼第三分量也應該是遞增的。但是上圖中紅框里不是哦——事實上它們是「被湮沒」的「轉折點」(上圖的黃色圓形)。
所以哦,棄掉他們(稱作第二類拋棄),得到 ,就是下圖 。
而最終結果就是 的最後一項的第三個分量。
由得到 的過程是(例如):
已經按照第二分量遞增排序好,
之後先寫成
然後對第一個三元組,
刪除當前位置之後被「湮沒」的
對第二個三元組,一定是插入當前位置之後,並被立即「湮沒」,
不斷這樣進行下去,並注意第一類拋棄即可得到 。
令,則可以得到(由於分行了,就不在乎三元組的第一分量了):
然後所謂「一維」存儲,其實就是把它「存儲成了」一維,例如使用兩個一維數組和一個start數組做「分割」:
然後就是如何得到方案——
看 的最後一個是不是與 的最後一個相同,相同的話就直接看 ;
的最後一個與 的最後一個不同,所以一定拿了物品4,然後看 第二分量不超過5(= )的最後一個,是 ;
與 的最後一個不同,所以一定拿了物品3;
……然後類推。
最後是分析複雜度:
路線是計算 的元素個數,然後對 求和,就得到了所有「藍色格子」的數量。
然後,
- 首先,由於 在不考慮兩類拋棄的情況下(最差情況就是不發生這兩類拋棄),元素個數恰好等於 元素數的兩倍;也可以這樣來看——對於每一個 , 最多只有 個「轉折點」;
- 由 得到 時, 中各組的第二分量、第三分量一定彼此不同,那麼每個 中的 的取值範圍是 ,第三分量的取值範圍是 。所以這樣的三元組最多有 個。
對 求和,得到
- ;
- ;
而由 產生 的計算過程主要就是產生一個新的對、插入、刪除(拋棄),所以這個過程的計算量是和 元素數成正比的。
所以得到,無論空間複雜度還是時間複雜度,都是 的。
即使 ,這時的演算法複雜度也控制在 之內。
如果你是運籌學/人工智慧碩博或在讀,請在下圖的公眾號後台留言:「加微信群」。系統會自動辨認你的關鍵字,並提示您進一步的加群要求和步驟,邀請您進全球運籌或AI學者群(群內學界、業界大佬雲集)。
同時我們有:【運籌學|優化愛好者】【供應鏈|物流】【人工智慧】【數據科學|分析】千人QQ群,想入群的小夥伴可以關注下方公眾號點擊「加入社區」按鈕,獲得入群傳送門。
學術界|工業界招聘、徵稿等信息免費發布,請見下圖:
推薦閱讀:
※運籌學、人工智慧、數據科學尋學術合作,承接工業界諮詢,歡迎訪問海德堡大學組合優化實驗室、圖像處理中心
※【供應鏈】運籌學與供應鏈管理
※運籌學S01E05——動態規劃
※OPL建模語言從入門到放棄(二)
※【學界】機器學習、數據科學 如何進階成為大神?