前言

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

紙上得來終覺淺，絕知此事要躬行。

那么今天開始我們來聊聊具體的那些面試時常考的題目。

問題背景

月黑風(fēng)高的夜晚，張三開啟了法外狂徒模式：他背著一個可裝載重量為 W 的背包去地主家偷東西。

地主家有 N 個物品，每個物品有重量和價值兩個屬性，其中第 i 個物品的重量為 wt[i]，價值為 val[i]。

問張三現(xiàn)在用這個背包裝物品，最多能裝的價值是多少？

舉例：

N = 3 //地主家有三樣?xùn)|西

wt = [2,1,3] //每樣?xùn)|西的重量

val = [4,2,3] //每樣?xùn)|西的價值

W = 4 //背包可裝載重量

算法應(yīng)該返回 6.

因為選擇第一件物品和第二件物品，在重量沒有超出背包容量下，所選價值最大。

如果每種物品只能選 0 個或 1 個（即要么將此物品裝進(jìn)包里要么不裝），則此問題稱為 0-1 背包問題；如果不限每種物品的數(shù)量，則稱為無界（或完全）背包問題。

今天這篇文章我們只關(guān)注 0-1 背包問題，下一篇文章再聊完全背包問題。

那我們是如何選擇要裝入的物品的？

思路初探

首先，質(zhì)量很大價值很小的物品我們先不考慮（放著地主家金銀財寶珍珠首飾不偷，背出來一包煤...，那也就基本告別盜竊行業(yè)了...）

然后呢？再考慮質(zhì)量大價值也大的？還是質(zhì)量較小價值也稍小的？

我們自然而然想到：裝價值/質(zhì)量 比值最大的，因為這至少能說明，此物品的“價質(zhì)比”最大（也即貪心算法，每次選擇當(dāng)前最優(yōu)）

那么這樣裝能保證最后裝入背包里的價值最優(yōu)嗎？

我們先來看一個例子：

假設(shè)有 5 個物品，N = 5，每種物品的質(zhì)量與價值如下：

W : 20, 30, 40, 50, 60

V : 20, 30, 44, 55, 60

V/W: 1, 1, 1.1, 1.1, 1

背包容量為 100

如果按上述策略：優(yōu)先選“價質(zhì)比”最大的：即第三個和第四個物品

此時質(zhì)量：40+50=90

價值：44+55 =99

但我們知道，此題更優(yōu)的選擇策略是：選第一個，第二個和第四個

此時質(zhì)量：20+30+50=100

價值：20+30+55=105

所以，我們的“價質(zhì)比”這種貪心策略顯然不是最優(yōu)策略。

讀過一文學(xué)懂動態(tài)規(guī)劃這篇文章的讀者會發(fā)現(xiàn)，之前文章中兌換零錢例子我們最開始也是采取貪心策略，但最后發(fā)現(xiàn)貪心不是最優(yōu)解，由此我們引出了動態(tài)規(guī)劃。

沒錯，今天這題也正是動態(tài)規(guī)劃又一經(jīng)典的應(yīng)用。

解題思路

根據(jù)動之前的文章我們知道，動態(tài)規(guī)劃的核心即：狀態(tài)與狀態(tài)轉(zhuǎn)移方程。

那么此題的狀態(tài)是什么呢？

狀態(tài)

何為狀態(tài)？

說白了，狀態(tài)就是已知條件。

重讀題意我們發(fā)現(xiàn)：此題的已知條件只有兩個：

• 背包容量
• 可選的物品

題目要求的是在滿足背包容量前提下，可裝入的最大價值。

那么我們可以根據(jù)上述狀態(tài)定義出 dp 數(shù)組，即：

dp[i][w] 表示：對于前i個物品，當(dāng)前背包的容量為w，這種情況下可以裝的最大價值是dp[i][w]

我們自然而然的考慮到如下特殊情況：

當(dāng) i = 0 或 w = 0，那么：

dp[0][...] = dp[...][0] = 0

解釋：
對前 0 個物品而言，無論背包容量等于多少，裝入的價值為 0；

當(dāng)背包容量為 0 時，無論裝入前多少個物品（因為一個都裝不進(jìn)去），背包里的價值依舊為 0。

根據(jù)這個定義，我們求的最終答案就是dp[N][W]

我們現(xiàn)在找出了狀態(tài)，并找到了 base case，那么狀態(tài)之間該如何轉(zhuǎn)移呢（狀態(tài)轉(zhuǎn)移方程）？

狀態(tài)轉(zhuǎn)移方程

dp[i][w] 表示：對于前i個物品，當(dāng)前背包的容量為w，這種情況下可以裝的最大價值是dp[i][w]。

思考：對于當(dāng)前第 i 個物品：

• 如果沒有把第 i 個物品裝入包里（第 i 個物品質(zhì)量大于當(dāng)前背包容量）：那么很顯然，最大價值dp[i][w]應(yīng)該等于dp[i - 1][w]，沒有裝進(jìn)去嘛，故當(dāng)前背包總價值就等于之前的結(jié)果，即第i - 1 個物品之前的總價值 。

• 如果把第 i 個物品裝入了包里，那么 dp[i][w]應(yīng)該等于什么呢？

它應(yīng)該等于下面兩者里的較大值：

1. dp[i - 1][w] //前i - 1個物品，背包所裝的最大價值

2. dp[i - 1]w - wt[i]] + val [i] //當(dāng)前第 i 個物品我裝里邊了，那么此時背包裝入的總價值即為：當(dāng)前第 i 個物品的價值 val [i] + 第 i 個物品之前，背包容量為w - wt[i]（w 減去當(dāng)前第 i 個物品的質(zhì)量）dp[i - 1]w - wt[i]] 時的價值

上述兩個如果可以寫成以下代碼：

例子

我們接來下再用一個具體的例子，來理解狀態(tài)和狀態(tài)轉(zhuǎn)移方程。

現(xiàn)在我們有 4 個物品，物品對應(yīng)的價值與質(zhì)量分別如上圖左側(cè)所示：

6, 4

2，5

1, 4

8, 1

Step 1

我們首先初始化一行和一列 0，分別對應(yīng)dp[0][w] 和 dp[i][0]。

那么第一個問號處應(yīng)該填什么呢？

我們根據(jù)上述表述的狀態(tài)轉(zhuǎn)移關(guān)系來判斷：

當(dāng)前第一個物品的重量 4 > 背包容量，故裝不進(jìn)去，所以繼承上一個結(jié)果。

上一個結(jié)果是什么呢？

就是第 i - 1個物品，也就是第 0 個，和W = 1時的價值：

if (wt[i] > W) {
 dp[i][W] = dp[i-1][W];  //繼承上一個結(jié)果
}

此時方框里的值為 0，故第一個問號這里應(yīng)該填 0

Step 2

現(xiàn)在我們走到了當(dāng)背包容量 W = 2 的時候，此時當(dāng)前 i (依舊第一個物品)能否裝進(jìn)背包里呢？

我們發(fā)現(xiàn) 4 > 2，此時還是裝不進(jìn)去，那么同樣繼承上一個結(jié)果。

上一個結(jié)果是 i 不變(依舊是第 **0 **個物品),W = 2，所以結(jié)果依舊為 0。

Step 3

現(xiàn)在來到 W = 3，發(fā)現(xiàn)依舊裝不進(jìn)去，所以填 0。

Step 4

下一步到 W = 4 這里了，

此時物品重量 4 = 4(背包容量)，可以裝里，那么按照之前狀態(tài)轉(zhuǎn)移關(guān)系應(yīng)該是：

Option A:

• 上一個結(jié)果 : dp[i - 1][w]，即dp[0][4] = 0

Option B:

• 把當(dāng)前第 i 個物品裝入背包里所得到價值：dp[i - 1]W - wt[i]] + val [i]

此時第一個物品的重量為 4，背包容量為 4,

故要想裝入重量為 4 的此物品，那么背包先前的容量必須為當(dāng)前背包容量 - 當(dāng)前物品容量：4 - 4 = 0。

我們隨即找到在沒裝入此物品（重量為 4，價值為 6）之前的dp[i -1]W - wt[i]] = dp[0][0] = 0

那么dp[i -1]W - wt[i]] + val [i] = 0 + 6 = 6

6 和 0 選擇一個最大值，所以這里問號處應(yīng)填入6

Step 5

下一步我們來到 W = 5 這里，此時依舊是第一個物品，質(zhì)量 4 < 5(背包容量)，我們可以裝里邊。

然后我們在

Option A:

• 上一個結(jié)果 ：dp[0][5] = 0

Option B:

• 把當(dāng)前第 i 個物品裝入背包里所得到價值：dp[i -1]W - wt[i]] + val [i]

此時第一個物品的重量為 4，背包容量為 5

故要想裝入重量為 4 的此物品，那么背包先前的容量必須為：當(dāng)前背包容量 - 當(dāng)前物品容量：5 - 4 = 1 ，

我們隨即找到在沒裝入此物品(重量為 4，價值為 6)之前的dp[i - 1]W - wt[i]] = dp[0][1] = 0

那么dp[i -1]W - wt[i]] + val [i] = 0 + 6 = 6

選擇一個最大值，即 6，所以此處應(yīng)該填入 6

我們根據(jù)以上狀態(tài)轉(zhuǎn)系關(guān)系，依次可以填出空格其它值，最后我們得到整個 dp 數(shù)組：

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

(注意：我們在這里求的是 0-1 背包問題，即某一個物品只能選擇 0 個或 1 個，不能多選！)

代碼

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

兩層 for 循環(huán)

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

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

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

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

由此我們給出完整代碼：

class solution{
  public int knapsackProblem(int[] wt,int[] val,int size){
    //定義dp數(shù)組
    int[][] dp = new int[wt.length][size];
    //對于裝入前0個物品而言，dp數(shù)組儲存的總價值初始化為0
    for(int i = 0;i < size;i++){
     int[0][i] = 0;
    }
    //對于背包容量W=0時，裝入背包的總價值初始化為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個物品質(zhì)量大于當(dāng)前背包容量
         if (wt[i] > W) {
             dp[i][W] = dp[i-1][W];  //繼承上一個結(jié)果
         } else {
             //在“上一個結(jié)果價值”和“把當(dāng)前第i個物品裝入背包里所得到價值”二者里選價值較大的
             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)移的，最后的代碼水到渠成。

本文所說的這個 0-1 背包問題，Leetcode 上并沒有這個原題，所以對于背包問題，最重要的是它的變種。

背包問題是一大類問題的統(tǒng)稱，很大一部分動態(tài)規(guī)劃的題深層剖析都可以轉(zhuǎn)換為背包問題。

所以還需要理解體會背包問題的核心思想，再將此種思想運(yùn)用到其它一類背包問題的問題上。

那么背包問題還有哪些變化呢？我們下期見～