1、動(dòng)態(tài)規(guī)劃01背包問題01背包問題，是用來介紹動(dòng)態(tài)規(guī)劃算法最經(jīng)典的例子，網(wǎng)上關(guān)于01背包問題的講解也很多，我寫這篇文章力爭(zhēng)做到用最簡(jiǎn)單的方式，最少的公式把01背包問題講解透徹。01背包的狀態(tài)轉(zhuǎn)換方程 fi,j = Max fi-1,j-Wi+Pi( j >= Wi ),  fi-1,j fi,j表示在前i件物品中選擇若干件放在承重為 j 的背包中，可以取得的最大價(jià)值。Pi表示第i件物品的價(jià)值。決策：為了背包中物品總價(jià)值最大化，第 i件物品應(yīng)該放入背包中嗎 ？題目描述：有編號(hào)分別為a,b,c,d,e的五件物品，它們的重量分別是2,2,6,5,4，它們的價(jià)值分別是6,3,5

2、,4,6，現(xiàn)在給你個(gè)承重為10的背包，如何讓背包里裝入的物品具有最大的價(jià)值總和？nameweightvalue12345678910a26066991212151515b23033669991011c65000666661011d54000666661010e460006666666只要你能通過找規(guī)律手工填寫出上面這張表就算理解了01背包的動(dòng)態(tài)規(guī)劃算法。首先要明確這張表是至底向上，從左到右生成的。為了敘述方便，用e2單元格表示e行2列的單元格，這個(gè)單元格的意義是用來表示只有物品e時(shí)，有個(gè)承重為2的背包，那么這個(gè)背包的最大價(jià)值是0，因?yàn)閑物品的重量是4，背包裝不了。對(duì)于d2單元格，表示只有物品e

3、，d時(shí),承重為2的背包,所能裝入的最大價(jià)值，仍然是0，因?yàn)槲锲積,d都不是這個(gè)背包能裝的。同理，c2=0，b2=3,a2=6。對(duì)于承重為8的背包，a8=15,是怎么得出的呢？根據(jù)01背包的狀態(tài)轉(zhuǎn)換方程，需要考察兩個(gè)值，一個(gè)是fi-1,j,對(duì)于這個(gè)例子來說就是b8的值9，另一個(gè)是fi-1,j-Wi+Pi；在這里， fi-1,j表示我有一個(gè)承重為8的背包，當(dāng)只有物品b,c,d,e四件可選時(shí)，這個(gè)背包能裝入的最大價(jià)值fi-1,j-Wi表示我有一個(gè)承重為6的背包（等于當(dāng)前背包承重減去物品a的重量），當(dāng)只有物品b,c,d,e四件可選時(shí)，這個(gè)背包能裝入的最大價(jià)值fi-1,j-Wi就是指單元格b6

4、,值為9，Pi指的是a物品的價(jià)值，即6由于fi-1,j-Wi+Pi = 9 + 6 = 15 大于fi-1,j = 9，所以物品a應(yīng)該放入承重為8的背包以下是actionscript3 的代碼java view plain copy 1. public function get01PackageAnswer(bagItems:Array,bagSize:int):Array  2.   3.     var bagMatrix:Array=; &

5、#160;4.     var i:int;  5.     var item:PackageItem;  6.     for(i=0;i<bagItems.length;i+)  7.       8.         bagMatrixi 

6、;= 0;  9.       10.     for(i=1;i<=bagSize;i+)  11.       12.         for(var j:int=0;j<bagItems.length;j+)  13.    

7、60;      14.             item = bagItemsj as PackageItem;  15.             if(item.weight > i)  1

8、6.               17.                 /i背包轉(zhuǎn)不下item  18.               &#

9、160; if(j=0)  19.                   20.                     bagMatrixji = 0; 

10、60;21.                   22.                 else  23.            

11、;       24.                     bagMatrixji=bagMatrixj-1i;  25.                &

12、#160;  26.               27.             else  28.               29.   

13、;              /將item裝入背包后的價(jià)值總和  30.                 var itemInBag:int;  31.         

14、        if(j=0)  32.                   33.                    

15、60;bagMatrixji = item.value;  34.                     continue;  35.                  

16、; 36.                 else  37.                   38.           &

17、#160;         itemInBag = bagMatrixj-1i-item.weight+item.value;  39.                   40.          

18、       bagMatrixji = (bagMatrixj-1i > itemInBag ? bagMatrixj-1i : itemInBag)  41.               42.        

19、   43.       44.     /find answer  45.     var answers:Array=;  46.     var curSize:int = bagSize;  47.     for(i=bagIte

20、ms.length-1;i>=0;i-)  48.       49.         item = bagItemsi as PackageItem;  50.         if(curSize=0)  51.     

21、0;     52.             break;  53.           54.         if(i=0 && curSize > 0) 

22、; 55.           56.             answers.push();  57.             break;  58.    &

23、#160;      59.         if(bagMatrixicurSize-bagMatrixi-1curSize-item.weight=item.value)  60.           61.           

24、60; answers.push();  62.             curSize -= item.weight;  63.           64.       65.     re

25、turn answers;  66.   PackageItem類java view plain copy 1. public class PackageItem  2.   3.     public var name:String;  4.     public var weight:int;  

26、;5.     public var value:int;  6.     public function PackageItem(name:String,weight:int,value:int)  7.       8.          = name;  9.  &#