前言

經(jīng)過(guò)前面三篇?jiǎng)討B(tài)規(guī)劃文章的介紹，相信大家對(duì)動(dòng)態(tài)規(guī)劃、分治、貪心有了充分的理解，對(duì)動(dòng)態(tài)規(guī)劃的 3 個(gè)核心問(wèn)題、其本質(zhì)也有了了解。

紙上得來(lái)終覺(jué)淺，絕知此事要躬行。

那么今天開(kāi)始我們來(lái)聊聊具體的那些面試時(shí)?？嫉念}目。

問(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)該等于下面兩者里的較大值：

1. dp[i - 1][w] //前i - 1個(gè)物品，背包所裝的最大價(jià)值

2. 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ě)成以下代碼：

例子

我們接來(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)該是：

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ù)組：

最后的 dp[4][6]：考慮前四個(gè)物品，背包容量為 6 的情況下，可裝入的最大價(jià)值，即為所求。

(注意：我們?cè)谶@里求的是 0-1 背包問(wèn)題，即某一個(gè)物品只能選擇 0 個(gè)或 1 個(gè)，不能多選！)

代碼

根據(jù)以上思路，我們很容易寫(xiě)出代碼：

兩層 for 循環(huán)

1. 外層循環(huán) i 遍歷物品(即前幾個(gè)物品)：

for(int i = 1;i <=N;i++){
  ...
}

1. 內(nèi)層循環(huán) j 遍歷 1~W(背包容量)之間的整數(shù)值：

然后寫(xiě)入狀態(tài)轉(zhuǎn)移方程

由此我們給出完整代碼：

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)～