經(jīng)典動(dòng)態(tài)規(guī)劃：0-1 背包問(wèn)題
問(wèn)題背景
月黑風(fēng)高的夜晚，張三開(kāi)啟了法外狂徒模式：他背著一個(gè)可裝載重量為 W 的背包去地主家偷東西。
地主家有 N 個(gè)物品，每個(gè)物品有重量和價(jià)值兩個(gè)屬性，其中第 i 個(gè)物品的重量為 wt[i]，價(jià)值為 val[i]。
問(wèn)張三現(xiàn)在用這個(gè)背包裝物品，最多能裝的價(jià)值是多少?
舉例：
- N = 3 //地主家有三樣?xùn)|西
- wt = [2,1,3] //每樣?xùn)|西的重量
- val = [4,2,3] //每樣?xùn)|西的價(jià)值
- W = 4 //背包可裝載重量
算法應(yīng)該返回 6.
因?yàn)檫x擇第一件物品和第二件物品，在重量沒(méi)有超出背包容量下，所選價(jià)值最大。
如果每種物品只能選 0 個(gè)或 1 個(gè)(即要么將此物品裝進(jìn)包里要么不裝)，則此問(wèn)題稱為 0-1 背包問(wèn)題;如果不限每種物品的數(shù)量，則稱為無(wú)界(或完全)背包問(wèn)題。
今天這篇文章我們只關(guān)注 0-1 背包問(wèn)題，下一篇文章再聊完全背包問(wèn)題。
那我們是如何選擇要裝入的物品的?
思路初探
首先，質(zhì)量很大價(jià)值很小的物品我們先不考慮(放著地主家金銀財(cái)寶珍珠首飾不偷，背出來(lái)一包煤...，那也就基本告別盜竊行業(yè)了...)
然后呢?再考慮質(zhì)量大價(jià)值也大的?還是質(zhì)量較小價(jià)值也稍小的?
我們自然而然想到：裝價(jià)值/質(zhì)量 比值最大的，因?yàn)檫@至少能說(shuō)明，此物品的“價(jià)質(zhì)比”最大(也即貪心算法，每次選擇當(dāng)前最優(yōu))
那么這樣裝能保證最后裝入背包里的價(jià)值最優(yōu)嗎?
我們先來(lái)看一個(gè)例子：
假設(shè)有 5 個(gè)物品，N = 5，每種物品的質(zhì)量與價(jià)值如下：
- W : 20, 30, 40, 50, 60
- V : 20, 30, 44, 55, 60
- V/W: 1, 1, 1.1, 1.1, 1
背包容量為 100
如果按上述策略：優(yōu)先選“價(jià)質(zhì)比”最大的：即第三個(gè)和第四個(gè)物品
- 此時(shí)質(zhì)量：40+50=90
- 價(jià)值：44+55 =99
但我們知道，此題更優(yōu)的選擇策略是：選第一個(gè)，第二個(gè)和第四個(gè)
- 此時(shí)質(zhì)量：20+30+50=100
- 價(jià)值：20+30+55=105
所以，我們的“價(jià)質(zhì)比”這種貪心策略顯然不是最優(yōu)策略。
讀過(guò)一文學(xué)懂動(dòng)態(tài)規(guī)劃這篇文章的讀者會(huì)發(fā)現(xiàn)，之前文章中兌換零錢例子我們最開(kāi)始也是采取貪心策略，但最后發(fā)現(xiàn)貪心不是最優(yōu)解，由此我們引出了動(dòng)態(tài)規(guī)劃。
沒(méi)錯(cuò)，今天這題也正是動(dòng)態(tài)規(guī)劃又一經(jīng)典的應(yīng)用。
解題思路
根據(jù)動(dòng)之前的文章我們知道，動(dòng)態(tài)規(guī)劃的核心即：狀態(tài)與狀態(tài)轉(zhuǎn)移方程。
那么此題的狀態(tài)是什么呢?
狀態(tài)
何為狀態(tài)?
說(shuō)白了，狀態(tài)就是已知條件。
重讀題意我們發(fā)現(xiàn)：此題的已知條件只有兩個(gè)：
- 背包容量
- 可選的物品
題目要求的是在滿足背包容量前提下，可裝入的最大價(jià)值。
那么我們可以根據(jù)上述狀態(tài)定義出 dp 數(shù)組，即：
dp[i][w] 表示：對(duì)于前i個(gè)物品，當(dāng)前背包的容量為w，這種情況下可以裝的最大價(jià)值是dp[i][w]
我們自然而然的考慮到如下特殊情況：
當(dāng) i = 0 或 w = 0，那么：
dp[0][...] = dp[...][0] = 0
解釋：
對(duì)前 0 個(gè)物品而言，無(wú)論背包容量等于多少，裝入的價(jià)值為 0;
當(dāng)背包容量為 0 時(shí)，無(wú)論裝入前多少個(gè)物品(因?yàn)橐粋€(gè)都裝不進(jìn)去)，背包里的價(jià)值依舊為 0。
根據(jù)這個(gè)定義，我們求的最終答案就是dp[N][W]
我們現(xiàn)在找出了狀態(tài)，并找到了 base case，那么狀態(tài)之間該如何轉(zhuǎn)移呢(狀態(tài)轉(zhuǎn)移方程)?
狀態(tài)轉(zhuǎn)移方程
dp[i][w] 表示：對(duì)于前i個(gè)物品，當(dāng)前背包的容量為w，這種情況下可以裝的最大價(jià)值是dp[i][w]。
思考：對(duì)于當(dāng)前第 i 個(gè)物品：
- 如果沒(méi)有把第 i 個(gè)物品裝入包里(第 i 個(gè)物品質(zhì)量大于當(dāng)前背包容量)：那么很顯然，最大價(jià)值dp[i][w]應(yīng)該等于dp[i - 1][w]，沒(méi)有裝進(jìn)去嘛，故當(dāng)前背包總價(jià)值就等于之前的結(jié)果，即第i - 1 個(gè)物品之前的總價(jià)值 。
- 如果把第 i 個(gè)物品裝入了包里，那么 dp[i][w]應(yīng)該等于什么呢?
它應(yīng)該等于下面兩者里的較大值：
- dp[i - 1][w] //前i - 1個(gè)物品，背包所裝的最大價(jià)值
- dp[i - 1]w - wt[i]] + val [i] //當(dāng)前第 i 個(gè)物品我裝里邊了，那么此時(shí)背包裝入的總價(jià)值即為：當(dāng)前第 i 個(gè)物品的價(jià)值 val [i] + 第 i 個(gè)物品之前，背包容量為w - wt[i](w 減去當(dāng)前第 i 個(gè)物品的質(zhì)量)dp[i - 1]w - wt[i]] 時(shí)的價(jià)值
上述兩個(gè)如果可以寫(xiě)成以下代碼：
- //如果第i個(gè)物品質(zhì)量大于當(dāng)前背包容量
- if (wt[i] > W) {
- dp[i][W] = dp[i-1][W]; //繼承上一個(gè)結(jié)果
- } else {
- //在“上一個(gè)結(jié)果價(jià)值”和“把當(dāng)前第i個(gè)物品裝入背包里所得到價(jià)值”二者里選價(jià)值較大的
- dp[i][W] = Math.max(dp[i-1][W],dp[i-1][W-wt[i]] + val[i])
- }
例子
我們接來(lái)下再用一個(gè)具體的例子，來(lái)理解狀態(tài)和狀態(tài)轉(zhuǎn)移方程。
現(xiàn)在我們有 4 個(gè)物品，物品對(duì)應(yīng)的價(jià)值與質(zhì)量分別如上圖左側(cè)所示：
- 6, 4
- 2，5
- 1, 4
- 8, 1
Step 1
我們首先初始化一行和一列 0，分別對(duì)應(yīng)dp[0][w] 和 dp[i][0]。
那么第一個(gè)問(wèn)號(hào)處應(yīng)該填什么呢?
我們根據(jù)上述表述的狀態(tài)轉(zhuǎn)移關(guān)系來(lái)判斷：
當(dāng)前第一個(gè)物品的重量 4 > 背包容量，故裝不進(jìn)去，所以繼承上一個(gè)結(jié)果。
上一個(gè)結(jié)果是什么呢?
就是第 i - 1個(gè)物品，也就是第 0 個(gè)，和W = 1時(shí)的價(jià)值：
- if (wt[i] > W) {
- dp[i][W] = dp[i-1][W]; //繼承上一個(gè)結(jié)果
- }
此時(shí)方框里的值為 0，故第一個(gè)問(wèn)號(hào)這里應(yīng)該填 0
Step 2
現(xiàn)在我們走到了當(dāng)背包容量 W = 2 的時(shí)候，此時(shí)當(dāng)前 i (依舊第一個(gè)物品)能否裝進(jìn)背包里呢?
我們發(fā)現(xiàn) 4 > 2，此時(shí)還是裝不進(jìn)去，那么同樣繼承上一個(gè)結(jié)果。
上一個(gè)結(jié)果是 i 不變(依舊是第 **0 **個(gè)物品),W = 2，所以結(jié)果依舊為 0。
Step 3
現(xiàn)在來(lái)到 W = 3，發(fā)現(xiàn)依舊裝不進(jìn)去，所以填 0。
Step 4
下一步到 W = 4 這里了，
此時(shí)物品重量 4 = 4(背包容量)，可以裝里，那么按照之前狀態(tài)轉(zhuǎn)移關(guān)系應(yīng)該是：
- else {
- //在“上一個(gè)結(jié)果價(jià)值”和“把當(dāng)前第i個(gè)物品裝入背包里所得到價(jià)值”二者里選價(jià)值較大的
- dp[i][W] = Math.max(dp[i-1][W],dp[i-1][W-wt[i]] + val[i])
- }
Option A:
- 上一個(gè)結(jié)果 : dp[i - 1][w]，即dp[0][4] = 0
Option B:
- 把當(dāng)前第 i 個(gè)物品裝入背包里所得到價(jià)值：dp[i - 1]W - wt[i]] + val [i]
此時(shí)第一個(gè)物品的重量為 4，背包容量為 4,
故要想裝入重量為 4 的此物品，那么背包先前的容量必須為當(dāng)前背包容量 - 當(dāng)前物品容量：4 - 4 = 0。
我們隨即找到在沒(méi)裝入此物品(重量為 4，價(jià)值為 6)之前的dp[i -1]W - wt[i]] = dp[0][0] = 0
那么dp[i -1]W - wt[i]] + val [i] = 0 + 6 = 6
6 和 0 選擇一個(gè)最大值，所以這里問(wèn)號(hào)處應(yīng)填入6
Step 5
下一步我們來(lái)到 W = 5 這里，此時(shí)依舊是第一個(gè)物品，質(zhì)量 4 < 5(背包容量)，我們可以裝里邊。
然后我們?cè)?/p>
Option A:
- 上一個(gè)結(jié)果 ：dp[0][5] = 0
Option B:
- 把當(dāng)前第 i 個(gè)物品裝入背包里所得到價(jià)值：dp[i -1]W - wt[i]] + val [i]
此時(shí)第一個(gè)物品的重量為 4，背包容量為 5
故要想裝入重量為 4 的此物品，那么背包先前的容量必須為：當(dāng)前背包容量 - 當(dāng)前物品容量：5 - 4 = 1 ，
我們隨即找到在沒(méi)裝入此物品(重量為 4，價(jià)值為 6)之前的dp[i - 1]W - wt[i]] = dp[0][1] = 0
那么dp[i -1]W - wt[i]] + val [i] = 0 + 6 = 6
選擇一個(gè)最大值，即 6，所以此處應(yīng)該填入 6
我們根據(jù)以上狀態(tài)轉(zhuǎn)系關(guān)系，依次可以填出空格其它值，最后我們得到整個(gè) dp 數(shù)組：
| V | W | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | 4 | 0 | 0 | 0 | 0 | 6 | 6 | 6 |
| 2 | 5 | 0 | 0 | 0 | 0 | 6 | 6 | 6 |
| 1 | 4 | 0 | 0 | 0 | 0 | 6 | 6 | 6 |
| 8 | 1 | 0 | 8 | 8 | 8 | 8 | 14 | 14 |
最后的 dp[4][6]：考慮前四個(gè)物品，背包容量為 6 的情況下，可裝入的最大價(jià)值，即為所求。
(注意：我們?cè)谶@里求的是 0-1 背包問(wèn)題，即某一個(gè)物品只能選擇 0 個(gè)或 1 個(gè)，不能多選!)
代碼
根據(jù)以上思路，我們很容易寫(xiě)出代碼：
兩層 for 循環(huán)
外層循環(huán) i 遍歷物品(即前幾個(gè)物品)：
- for(int i = 1;i <=N;i++){
- ...
- }
內(nèi)層循環(huán) j 遍歷 1~W(背包容量)之間的整數(shù)值：
然后寫(xiě)入狀態(tài)轉(zhuǎn)移方程
- for(int j = 0;j <= W;j++){
- //外層循環(huán)i,如果第i個(gè)物品質(zhì)量大于當(dāng)前背包容量
- if (wt[i] > W) {
- dp[i][W] = dp[i-1][W]; //繼承上一個(gè)結(jié)果
- } else {
- //在“上一個(gè)結(jié)果價(jià)值”和“把當(dāng)前第i個(gè)物品裝入背包里所得到價(jià)值”二者里選價(jià)值較大的
- dp[i][W] = Math.max(dp[i-1][W],dp[i-1][W-wt[i]] + val[i])
- }
- }
由此我們給出完整代碼：
- class solution{
- public int knapsackProblem(int[] wt,int[] val,int size){
- //定義dp數(shù)組
- int[][] dp = new int[wt.length][size];
- //對(duì)于裝入前0個(gè)物品而言，dp數(shù)組儲(chǔ)存的總價(jià)值初始化為0
- for(int i = 0;i < size;i++){
- int[0][i] = 0;
- }
- //對(duì)于背包容量W=0時(shí)，裝入背包的總價(jià)值初始化為0
- for(int j = 0;j < size;j++){
- int[j][0] = 0;
- }
- //外層循環(huán)遍歷物品
- for(int i = 1;i <= N;i++){
- //內(nèi)層循環(huán)遍歷1~W(背包容量)
- for(int j = 0;j <= W;j++){
- //外層循環(huán)i,如果第i個(gè)物品質(zhì)量大于當(dāng)前背包容量
- if (wt[i] > W) {
- dp[i][W] = dp[i-1][W]; //繼承上一個(gè)結(jié)果
- } else {
- //在“上一個(gè)結(jié)果價(jià)值”和“把當(dāng)前第i個(gè)物品裝入背包里所得到價(jià)值”二者里選價(jià)值較大的
- dp[i][W] = Math.max(dp[i-1][W],dp[i-1][W-wt[i]] + val[i])
- }
- }
- }
- }
- }
只要我們定義好了狀態(tài)(dp 數(shù)組的定義)，理清了狀態(tài)之間是如何轉(zhuǎn)移的，最后的代碼水到渠成。
本文所說(shuō)的這個(gè) 0-1 背包問(wèn)題，Leetcode 上并沒(méi)有這個(gè)原題，所以對(duì)于背包問(wèn)題，最重要的是它的變種。
背包問(wèn)題是一大類問(wèn)題的統(tǒng)稱，很大一部分動(dòng)態(tài)規(guī)劃的題深層剖析都可以轉(zhuǎn)換為背包問(wèn)題。
所以還需要理解體會(huì)背包問(wèn)題的核心思想，再將此種思想運(yùn)用到其它一類背包問(wèn)題的問(wèn)題上。
那么背包問(wèn)題還有哪些變化呢?我們下期見(jiàn)～
