JavaScript 背包問題詳解

（點擊上方 前端大學，可快速關注）

作者： 司徒正美

原文：https://segmentfault.com/a/1190000012829866

引子

打算好好學一下算法，先拿背包問題入手。但是網上許多教程都是C++或java或python，大部分作者都是在校生，雖然算法很強，但是完全沒有工程意識，全局變量滿天飛，變量名不明所以。我查了許多資料，花了一個星期才搞懂，最開始的01背包耗時最多，以前只會枚舉（就是普通的for循環，暴力地一步步遍歷下去），遞歸與二分，而動態規劃所講的狀態表與狀態遷移方程為我打開一扇大門。

篇幅可能有點長，但請耐心看一下，你會覺得物有所值的。本文以後還會擴展，因為我還沒有想到完全背包與多重背包列印物品編號的方法。如果有高人知道，勞煩在評論區指教一下。

注意，由於社區不支持LaTex數學公式，你們看到${xxxx}$,就自己將它們過濾吧。

1.1 問題描述：

有${n}$件物品和${1}$個容量為W的背包。每種物品均只有一件，第${i}$件物品的重量為${weights[i]}$，價值為${values[i]}$，求解將哪些物品裝入背包可使價值總和最大。

對於一種物品，要麼裝入背包，要麼不裝。所以對於一種物品的裝入狀態只是1或0, 此問題稱為01背包問題。

1.2 問題分析：

數據：物品個數${n=5}$,物品重量${weights=[2，2，6，5，4]}$,物品價值${values=[6，3，5，4，6]}$,背包總容量${W=10}$。

我們設置一個矩陣${f}$來記錄結果，${f(i, j)}$ 表示可選物品為 ${i...n}$ 背包容量為 ${j(0<=j<=W)}$ 時， 背包中所放物品的最大價值。

wvi012345678910260










231










652










543










464

我們先看第一行，物品0的體積為2，價值為6，當容量為0時，什麼也放不下，因此第一個格式只能填0，程序表示為${f(0,0) = 0}$或者${f[0][0] = 0}$。 當${j=1}$時，依然放不下${w0}$，因此依然為0，${f(0, 1) = 0}$。 當${j=2}$時，能放下${w0}$，於是有 ${f(0, 2)\ = \ v0=6}$。 當${j=3}$時，也能放下${w0}$，但我們只有一個物品0，因此它的值依然是6，於是一直到${j=10}$時，它的值都是${v_0}$。

wvi01234567891026000666666666231










652










543










464

根據第一行，我們得到如下方程

然後我們看第二行，確定確定${f(1,0...10)}$這11個元素的值。當${j=0}$ 時，依然什麼也放不下，值為0，但我們發覺它是上方格式的值一樣的，${f(1,0)=0}$。 當${j=1}$時，依然什麼也放不下，值為0，但我們發覺它是上方格式的值一樣的，${f(1,1)=0}$. 當${j=2}$時，它可以選擇放入物品1或不放。

如果選擇不放物品1，背包裡面有物品0，最大價值為6。

如果選擇放入物品1，我們要用算出背包放入物品1後還有多少容量，然後根據容量查出它的價值，再加上物品1的價值，即${f(0,j-w1)+v1}$ 。由於我們的目標是儘可能裝最值錢的物品， 因此放與不放， 我們需要通過比較來決定，於是有

顯然${v1=2，v0=6}$, 因此這裡填${v0}$。 當${j=3}$時， 情況相同。 當${j=4}$，能同時放下物品0與物品1，我們這個公式的計算結果也合乎我們的預期， 得到${f(1,4)=9}$。 當${j>4}$時， 由於背包只能放物品0與物品1，那麼它的最大價值也一直停留在${v0+v_1=9}$

wvi0123456789102600066666666623100669999999652










543










464

我們再看第三行，當${j=0}$時，什麼都放不下，${f(2,0)=0}$。當${j=1}$時，依然什麼也放不下，${f(2,1)=0}$，當${j=2}$時，雖然放不下${w_2}$，但我們根據上表得知這個容號時，背包能裝下的最大價值是6。繼續計算下去，其實與上面推導的公式結果是一致的，說明公式是有效的。當${j=8}$時，背包可以是放物品0、1，或者放物品1、2，或者放物品0、2。物品0、1的價值，我們在表中就可以看到是9，至於其他兩種情況我們姑且不顧，我們目測就知道是最優值是${6+5=11}$， 恰恰我們的公式也能正確計算出來。當${j=10}$時,剛好三個物品都能裝下，它們的總值為14，即${f(2,10)=14}$

第三行的結果如下：

wvi012345678910260006666666662310066999999965200669999111114543










464

整理一下第1，2行的適用方程：

我們根據此方程，繼續計算下面各列，於是得到

wvi0123456789102600066666666623100669999999652006699991111145430066999101113144640066991212151515

至此，我們就可以得到解為15.

我們最後根據0-1背包問題的最優子結構性質，建立計算${f(i,j)}$的遞歸式：

function knapsack(weights, values, W){

   var n = weights.length -1

   var f = [[]]

   for(var j = 0; j <= W; j++){

       if(j < weights[0]){ //如果容量不能放下物品0的重量，那麼價值為0

          f[0][j] = 0

       }else{ //否則等於物體0的價值

          f[0][j] = values[0]

       }

   }

   for(var j = 0; j <= W; j++){

       for(var i = 1; i <= n; i++ ){

           if(!f[i]){ //創建新一行

               f[i] = []

           }

           if(j < weights[i]){ //等於之前的最優值

               f[i][j] = f[i-1][j]

           }else{

               f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i])

           }

       }

   }

   return f[n][W]

}

var a = knapsack([2,2,6,5,4],[6,3,5,4,6],10)

console.log(a)

1.3 各種優化：

合併循環

現在方法裡面有兩個大循環，它們可以合併成一個。

function knapsack(weights, values, W){

   var n = weights.length;

   var f = new Array(n)

   for(var i = 0 ; i < n; i++){

       f[i] = []

   }

  for(var i = 0; i < n; i++ ){

      for(var j = 0; j <= W; j++){

           if(i === 0){ //第一行

               f[i][j] = j < weights[i] ? 0 : values[i]

           }else{

               if(j < weights[i]){ //等於之前的最優值

                   f[i][j] = f[i-1][j]

               }else{

                   f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i])

               }

           }

       }

   }

   return f[n-1][W]

}

然後我們再認真地思考一下，為什麼要孤零零地專門處理第一行呢？ f[i][j]=j<weights[i]?0:values[i]是不是能適用於下面這一行 f[i][j]=Math.max(f[i-1][j],f[i-1][j-weights[i]]+values[i])。Math.max可以輕鬆轉換為三元表達式，結構極其相似。而看一下i-1的邊界問題，有的書與博客為了解決它，會添加第0行，全部都是0，然後i再往下挪。其實我們也可以添加一個${-1}$行。那麼在我們的方程中就不用區分${i==0}$與${0>0}$的情況，方程與其他教科書的一模一樣了！

function knapsack(weights, values, W){

   var n = weights.length;

   var f = new Array(n)

   f[-1] = new Array(W+1).fill(0)

   for(var i = 0 ; i < n ; i++){ //注意邊界，沒有等號

       f[i] = new Array(W).fill(0)

       for(var j=0; j<=W; j++){//注意邊界，有等號

           if( j < weights[i] ){ //注意邊界， 沒有等號

               f[i][j] = f[i-1][j]

           }else{

               f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]);//case 3

           }

       }

   }

   return f[n-1][W]

}

wvi012345678910XX-1000000000002600066666666623100669999999652006699991111145430066999101113144640066991212151515

負一行的出現可以大大減少了在雙層循環的分支判定。是一個很好的技巧。

注意，許多舊的教程與網上文章，通過設置二維數組的第一行為0來解決i-1的邊界問題（比如下圖）。當然也有一些思維轉不過來的緣故，他們還在堅持數字以1開始，而我們新世代的IT人已經確立從0開始的編程思想。

選擇物品

上面講解了如何求得最大價值，現在我們看到底選擇了哪些物品，這個在現實中更有意義。許多書與博客很少提到這一點，就算給出的代碼也不對，估計是在設計狀態矩陣就出錯了。

仔細觀察矩陣，從${f(n-1,W)}$逆著走向${f(0,0)}$，設i=n-1,j=W，如果${f(i,j)}$==${f(i-1,j-wi)+vi}$說明包裡面有第i件物品，因此我們只要當前行不等於上一行的總價值，就能挑出第i件物品，然後j減去該物品的重量，一直找到j = 0就行了。

function knapsack(weights, values, W){

   var n = weights.length;

   var f = new Array(n)

   f[-1] = new Array(W+1).fill(0)

   var selected = [];

   for(var i = 0 ; i < n ; i++){ //注意邊界，沒有等號

       f[i] = [] //創建當前的二維數組

       for(var j=0; j<=W; j++){ //注意邊界，有等號

           if( j < weights[i] ){ //注意邊界， 沒有等號

               f[i][j] = f[i-1][j]//case 1

           }else{

               f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]);//case 2

           }

       }

   }

   var j = W, w = 0

   for(var i=n-1; i>=0; i--){

        if(f[i][j] > f[i-1][j]){

            selected.push(i)

            console.log("物品",i,"其重量為", weights[i],"其價格為", values[i])

            j = j - weights[i];

            w +=  weights[i]

        }

    }

   console.log("背包最大承重為",W," 現在重量為", w, " 總價值為", f[n-1][W])

   return [f[n-1][W], selected.reverse() ]

}

var a = knapsack([2,3,4,1],[2,5,3, 2],5)

console.log(a)

var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)

console.log(b)

使用滾動數組壓縮空間

所謂滾動數組，目的在於優化空間，因為目前我們是使用一個${ij}$的二維數組來儲存每一步的最優解。在求解的過程中，我們可以發現，當前狀態只與前一行的狀態有關，那麼更之前存儲的狀態信息已經無用了，可以捨棄的，我們只需要存儲當前狀態和前一行狀態，所以只需使用${2j}$的空間，循環滾動使用，就可以達到跟${i*j}$一樣的效果。這是一個非常大的空間優化。

function knapsack(weights, values, W){

   var n = weights.length

   var lineA = new Array(W+1).fill(0)

   var lineB = [], lastLine = 0, currLine

   var f = [lineA, lineB]; //case1 在這裡使用es6語法預填第一行

   for(var i = 0; i < n; i++){

       currLine = lastLine === 0 ? 1 : 0 //決定當前要覆寫滾動數組的哪一行

       for(var j=0; j<=W; j++){

           f[currLine][j] = f[lastLine][j] //case2 等於另一行的同一列的值

           if( j>= weights[i] ){                        

               var a = f[lastLine][j]

               var b = f[lastLine][j-weights[i]] + values[i]

               f[currLine][j] = Math.max(a, b);//case3

           }

       }

       lastLine = currLine//交換行

  }

  return f[currLine][W];

}

var a = knapsack([2,3,4,1],[2,5,3, 2],5)

console.log(a)

var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)

console.log(b)

注意，這種解法由於丟棄了之前N行的數據，因此很難解出挑選的物品，只能求最大價值。

使用一維數組壓縮空間

觀察我們的狀態遷移方程:

weights為每個物品的重量，values為每個物品的價值，W是背包的容量，i表示要放進第幾個物品，j是背包現時的容量（假設我們的背包是魔術般的可放大，從0變到W）。

我們假令i = 0

f中的-1就變成沒有意義，因為沒有第-1行，而weights[0], values[0]繼續有效，${f(0,j)}$也有意義，因為我們全部放到一個一維數組中。於是:

這方程後面多加了一個限制條件，要求是從大到小循環。為什麼呢？

假設有物體${\cal z}$容量2，價值${vz}$很大，背包容量為5，如果j的循環順序不是逆序，那麼外層循環跑到物體${\cal z}$時， 內循環在${j=2}$時 ，${\cal z}$被放入背包。當${j=4}$時，尋求最大價值，物體z放入背包，${f(4)=max(f(4),f(2)+vz) }$， 這裡毫無疑問後者最大。 但此時${f(2)+v_z}$中的${f(2)}$ 已經裝入了一次${\cal z}$，這樣一來${\cal z}$被裝入兩次不符合要求， 如果逆序循環j， 這一問題便解決了。

javascript實現：

function knapsack(weights, values, W){

   var n = weights.length;

   var f = new Array(W+1).fill(0)

   for(var i = 0; i < n; i++) {

       for(var j = W; j >= weights[i]; j--){  

           f[j] = Math.max(f[j], f[j-weights[i]] +values[i]);

       }

       console.log(f.concat()) //調試

   }

   return f[W];

}

var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)

console.log(b)

1.4 遞歸法解01背包

由於這不是動態規則的解法，大家多觀察方程就理解了：

function knapsack(n, W, weights, values, selected) {

   if (n == 0 || W == 0) {

       //當物品數量為0，或者背包容量為0時，最優解為0

       return 0;

   } else {

       //從當前所剩物品的最後一個物品開始向前，逐個判斷是否要添加到背包中

       for (var i = n - 1; i >= 0; i--) {

           //如果當前要判斷的物品重量大於背包當前所剩的容量，那麼就不選擇這個物品

           //在這種情況的最優解為f(n-1,C)

           if (weights[i] > W) {

               return knapsack(n - 1, W, weights, values, selected);

           } else {

               var a = knapsack(n - 1, W, weights, values, selected); //不選擇物品i的情況下的最優解

               var b = values[i] + knapsack(n - 1, W - weights[i], weights, values, selected); //選擇物品i的情況下的最優解

               //返回選擇物品i和不選擇物品i中最優解大的一個

               if (a > b) {

                   selected[i] = 0; //這種情況下表示物品i未被選取

                   return a;

               } else {

                   selected[i] = 1; //物品i被選取

                   return b;

               }

           }

       }

   }

}        

var selected = [], ws = [2,2,6,5,4], vs = [6,3,5,4,6]

var b = knapsack( 5, 10, ws, vs, selected)

console.log(b) //15

selected.forEach(function(el,i){

   if(el){

       console.log("選擇了物品"+i+ " 其重量為"+ ws[i]+" 其價值為"+vs[i])

   }

})

完全背包問題2.1 問題描述：

有${n}$件物品和${1}$個容量為W的背包。每種物品沒有上限，第${i}$件物品的重量為${weights[i]}$，價值為${values[i]}$，求解將哪些物品裝入背包可使價值總和最大。

2.2 問題分析：

最簡單思路就是把完全背包拆分成01背包，就是把01背包中狀態轉移方程進行擴展，也就是說01背包只考慮放與不放進去兩種情況，而完全背包要考慮 放0、放1、放2...的情況，

這個k當然不是無限的，它受背包的容量與單件物品的重量限制，即${j/weights[i]}$。假設我們只有1種商品，它的重量為20，背包的容量為60，那麼它就應該放3個，在遍歷時，就0、1、2、3地依次嘗試。

程序需要求解${nW}$個狀態，每一個狀態需要的時間為${O（W/w_i）}$，總的複雜度為${O(nWΣ(W/w_i))}$。

我們再回顧01背包經典解法的核心代碼

for(var i = 0 ; i < n ; i++){

  for(var j=0; j<=W; j++){

      f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]))

     }

  }

}

現在多了一個k，就意味著多了一重循環

for(var i = 0 ; i < n ; i++){

  for(var j=0; j<=W; j++){

      for(var k = 0; k < j / weights[i]; k++){

         f[i][j] = Math.max(f[i-1][j], f[i-1][j-k*weights[i]]+k*values[i]))

       }

     }

  }

}

javascript的完整實現：

function completeKnapsack(weights, values, W){

   var f = [], n = weights.length;

   f[-1] = [] //初始化邊界

   for(var i = 0; i <= W; i++){

       f[-1][i] = 0

   }

   for (var i = 0;i < n;i++){

       f[i] = new Array(W+1)

       for (var j = 0;j <= W;j++) {

           f[i][j] = 0;

           var bound = j / weights[i];

           for (var k = 0;k <= bound;k++) {

               f[i][j] = Math.max(f[i][j], f[i - 1][j - k * weights[i]] + k * values[i]);

           }

       }

   }

   return f[n-1][W];

}

//物品個數n = 3，背包容量為W = 5，則背包可以裝下的最大價值為40.

var a = completeKnapsack([3,2,2],[5,10,20], 5)

console.log(a) //40

2.3 O(nW)優化

我們再進行優化，改變一下f思路，讓${f(i,j)}$表示出在前i種物品中選取若干件物品放入容量為j的背包所得的最大價值。

所以說，對於第i件物品有放或不放兩種情況，而放的情況裡又分為放1件、2件、.${j/w_i}$件

如果不放, 那麼${f(i,j)=f(i-1,j)}$；如果放，那麼當前背包中應該出現至少一件第i種物品，所以f(i,j)中至少應該出現一件第i種物品,即${f(i,j)=f(i,j-wi)+vi}$，為什麼會是${f(i,j-wi)+vi}$？

因為我們要把當前物品i放入包內，因為物品i可以無限使用，所以要用${f(i,j-wi)}$；如果我們用的是${f(i-1,j-wi)}$，${f(i-1,j-wi)}$的意思是說，我們只有一件當前物品i，所以我們在放入物品i的時候需要考慮到第i-1個物品的價值${f(i-1,j-wi)}$；但是現在我們有無限件當前物品i，我們不用再考慮第i-1個物品了，我們所要考慮的是在當前容量下是否再裝入一個物品i，而${(j-w_i)}$的意思是指要確保${f(i,j)}$至少有一件第i件物品，所以要預留c(i)的空間來存放一件第i種物品。總而言之，如果放當前物品i的話，它的狀態就是它自己"i"，而不是上一個"i-1"。

所以說狀態轉移方程為：

與01背包的相比，只是一點點不同，我們也不需要三重循環了

javascript的完整實現：

function unboundedKnapsack(weights, values, W) {

   var f = [],

       n = weights.length;

   f[-1] = []; //初始化邊界

   for (let i = 0; i <= W; i++) {

       f[-1][i] = 0;

   }

   for (let i = 0; i < n; i++) {

       f[i] = [];

       for (let j = 0; j <= W; j++) {

           if (j < weights[i]) {

               f[i][j] = f[i - 1][j];

           } else {

               f[i][j] = Math.max(f[i - 1][j], f[i][j - weights[i]] + values[i]);

           }

       }

       console.log(f[i].concat());//調試

   }

   return f[n - 1][W];

}

var a = unboundedKnapsack([3, 2, 2], [5, 10, 20], 5); //輸出40

console.log(a);

var b = unboundedKnapsack([2, 3, 4, 7], [1, 3, 5, 9], 10); //輸出12

console.log(b);

我們可以繼續優化此算法，可以用一維數組寫

我們用${f(j)}$表示當前可用體積j的價值，我們可以得到和01背包一樣的遞推式：

function unboundedKnapsack(weights, values, W) {

   var n = weights.length,

   f = new Array(W + 1).fill(0);

   for(var i=0; i< n; ++i){

       for(j = weights[i]; j <= W; ++j) {

         var tmp = f[j-weights[i]]+values[i];

         f[j] = (f[j] > tmp) ? f[j] : tmp;

       }

   }

   console.log(f)//調試

   return f[W];

}

var a = unboundedKnapsack([3, 2, 2], [5, 10, 20], 5); //輸出40

console.log(a);

var b = unboundedKnapsack([2, 3, 4, 7], [1, 3, 5, 9], 10); //輸出12

console.log(b);

多重背包問題3.1 問題描述：

有${n}$件物品和${1}$個容量為W的背包。每種物品最多有numbers[i]件可用，第${i}$件物品的重量為${weights[i]}$，價值為${values[i]}$，求解將哪些物品裝入背包可使價值總和最大。

3.2 問題分析：

多重背包就是一個進化版完全背包。在我們做完全背包的第一個版本中，就是將它轉換成01背包，然後限制k的循環

直接套用01背包的一維數組解法

function knapsack(weights, values, numbers,  W){

   var n = weights.length;

   var f= new Array(W+1).fill(0)

   for(var i = 0; i < n; i++) {

       for(var k=0; k<numbers[i]; k++)//其實就是把這類物品展開，調用numbers[i]次01背包代碼  

        for(var j=W; j>=weights[i]; j--)//正常的01背包代碼  

            f[j]=Math.max(f[j],f[j-weights[i]]+values[i]);  

   }

   return f[W];

}

var b = knapsack([2,3,1 ],[2,3,4],[1,4,1],6)

console.log(b)

3.3 使用二進位優化

其實說白了我們最樸素的多重背包做法是將有數量限制的相同物品看成多個不同的0-1背包。這樣的時間複雜度為${O(WΣn(i))}$, W為空間容量 ，n(i)為每種背包的數量限制。如果這樣會超時，我們就得考慮更優的拆分方法，由於拆成1太多了，我們考慮拆成二進位數，對於13的數量，我們拆成1，2，4，6（有個6是為了湊數）。 19 我們拆成1，2，4，8，4 （最後的4也是為了湊和為19）。經過這個樣的拆分我們可以組合出任意的小於等於n(i)的數目（二進位啊，必然可以）。j極大程度縮減了等效為0-1背包時候的數量。 大概可以使時間複雜度縮減為${O(Wlog(ΣN(i))}$；

定理：一個正整數n可以被分解成1,2,4,…,2^(k-1),n-2^k+1（k是滿足n-2^k+1>0的最大整數）的形式，且1～n之內的所有整數均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某幾個數的和的形式。

證明如下：

（1） 數列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和為n，所以若干元素的和的範圍為：[1, n]；

（2）如果正整數t<= 2^k – 1,則t一定能用1,2,4,…,2^(k-1)中某幾個數的和表示，這個很容易證明：我們把t的二進位表示寫出來，很明顯，t可以表示成n=a0*2^0+a1*2^1+…+ak*2^（k-1），其中ak=0或者1，表示t的第ak位二進位數為0或者1.

（3）如果t>=2^k,設s=n-2^k+1，則t-s<=2^k-1，因而t-s可以表示成1,2,4,…,2^(k-1)中某幾個數的和的形式，進而t可以表示成1,2,4,…,2^(k-1)，s中某幾個數的和（加數中一定含有s）的形式。

（證畢！）

function mKnapsack(weights, values, numbers, W) {

   var kind = 0; //新的物品種類

   var ws = []; //新的物品重量

   var vs = []; //新的物品價值

   var n = weights.length;

   /**

    * 二進位分解

    * 100=1+2+4+8+16+32+37，觀察可以得出100以內任何一個數都可以由以上7個數選擇組合得到，

    * 所以對物品數目就不是從0都100遍歷，而是0，1，2，4，8，16，32，37遍歷，時間大大優化。

    */

   for (let i = 0; i < n; i++) {

       var w = weights[i];

       var v = values[i];

       var num = numbers[i];

       for (let j = 1; ; j *= 2) {

           if (num >= j) {

               ws[kind] = j * w;

               vs[kind] = j * v;

               num -= j;

               kind++;

           } else {

               ws[kind] = num * w;

               vs[kind] = num * v;

               kind++;

               break;

           }

       }

   }

   //01背包解法

   var f = new Array(W + 1).fill(0);

   for (let i = 0; i < kind; i++) {

       for (let j = W; j >= ws[i]; j--) {

           f[j] = Math.max(f[j], f[j - ws[i]] + vs[i]);

       }

   }

   return f[W];

}

var b = mKnapsack([2,3,1 ],[2,3,4],[1,4,1],6)

console.log(b) //9

參考連結

http://www.ahathinking.com/archives/95.html

http://www.hawstein.com/posts/f-knapsack.html

http://blog.csdn.net/shuilan0066/article/details/7767082

http://blog.csdn.net/siyu1993/article/details/52858940

http://blog.csdn.net/Dr_Unknown/article/details/51275471

https://www.cnblogs.com/shimu/p/5667215.html

http://www.saikr.com/t/2147

https://www.cnblogs.com/tgycoder/p/5329424.html

http://blog.csdn.net/chuck001002004/article/details/50340819

https://www.cnblogs.com/favourmeng/archive/2012/09/07/2675580.html

覺得本文對你有幫助？請分享給更多人

關注「前端大學」，提升前端技能