文/michaelgbw

要了解背包，首先得清楚動(dòng)態(tài)規(guī)劃：

動(dòng)態(tài)規(guī)劃算法可分解成從先到后的4個(gè)步驟：

• 描述一個(gè)最優(yōu)解的結(jié)構(gòu)；
• 遞歸地定義最優(yōu)解的值；
• 以“自底向上”的方式計(jì)算最優(yōu)解的值；
• 從已計(jì)算的信息中構(gòu)建出最優(yōu)解的路徑。

背包問題就是一個(gè)固定容量的背包，然后有一些商品，本身有兩個(gè)屬性，一個(gè)體積和價(jià)值，人總是貪婪的，總想獲得最多的價(jià)值。

其實(shí)背包問題有好多版本：

• 01背包（ZeroOnePack）: 有N件物品和一個(gè)容量為V的背包。每種物品均只有一件,第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。
• 完全背包(CompletePack): 有N種物品和一個(gè)容量為V的背包，每種物品都有無限件可用。第i種物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。
• 多重背包(MultiplePack): 有N種物品和一個(gè)容量為V的背包。第i種物品最多有n[i]件可用，每件費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。

比較三個(gè)題目，會發(fā)現(xiàn)不同點(diǎn)在于每種背包的數(shù)量，01背包是每種只有一件，完全背包是每種無限件，而多重背包是每種有限件。

此文值研究0-1背包問題，也就是最長見的背包問題。

01背包（ZeroOnePack）: 有N件物品和一個(gè)容量為V的背包。（每種物品均只有一件）第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。
這是最基礎(chǔ)的背包問題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。
用子問題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} （這是最根本的算法）

代碼

由于最近在面試，PHP，js都要會，所以這次的代碼我用js來寫~

//動(dòng)態(tài)規(guī)劃算法
 //數(shù)組中去除重復(fù)的算法
  Array.prototype.unique = function(){
    this.sort();
    var re=[this[0]];
    for(var i = 1; i < this.length; i++)
    {
      if( this[i] !== re[re.length-1])
      {
        re.push(this[i]);
      }
    }
    return re;
}
    function max(a,b){
      return (a > b) ? a: b;
    }
    function dynamicPack(capacity, size, value){
      var arr=new Array(); 
      var n=size.length;//item 的數(shù)量
      var k = new Array();
       //手動(dòng)構(gòu)建二維array
      for(var i=0;i<= capacity+1;i++){
        k[i]=[];
      }
      for(var i=0;i<=n;i++){
        for(var w=0;w <= capacity;w++){
          if(i==0 || w==0){
            k[i][w]=0;//表示當(dāng)物體為前面i個(gè),背包容量為w的最大價(jià)值
          } 
          else if(size[i-1] <= w){//大小為size[i-1]的物品可以放入背包時(shí)
            k[i][w]=max(value[i-1] +k[i-1][w-size[i-1]] , k[i-1][w]);
            if(k[i][w] !=k[i-1][w])
              arr.push(value[i-1]);
          }
          else{//大小為size[i-1]的物品不能放入背包時(shí)
            k[i][w]=k[i-1][w];
          }
           document.write(k[i][w]);
           document.write("...");
        }
          document.write("<br>");
      }
      var unarr=arr.unique();
      //console.log(unarr);
      var tem=0;
      var re=[];
      //k[n][capacity]是總價(jià)
      for(var i in unarr){
        if(tem <= k[n][capacity]){
          re.push(unarr[i]);
          tem+= parseInt(unarr[i]);
        }
      }
      //return re;//選取的商品價(jià)值
      return k[n][capacity];//最大價(jià)值
    }
    var value = [6,5,10,11,13];//價(jià)值
    var size = [3,4,7,8,9];//尺寸
    var capacity = 16;//背包容量
    var result=dynamicPack(capacity,size,value);
    console.log(result);

為了方便大家查看內(nèi)部究竟是怎樣運(yùn)作的，這里特地將每次的動(dòng)態(tài)數(shù)組都document.write()出來了

可以看到基本的算法就是：兩層循環(huán)，第一次的for是商品的個(gè)數(shù)，第二次for是背包的容量。然后k數(shù)組中的每次的數(shù)據(jù)k[i]的key其實(shí)是商品的尺寸，value是商品的價(jià)值，每次遇到新的商品就和之前的總價(jià)比較，看”有沒有必要“放入。之后一旦接受了新的商品，就暫存入數(shù)組，之后倒敘序便可以獲取到相應(yīng)的商品值了。

這既是基本算法了，return我提供了兩個(gè)一個(gè)是最大價(jià)，一個(gè)是最大價(jià)的每個(gè)商品的價(jià)值。這算是真正明白點(diǎn)了吧~