1.背景

? ? ?追隨著buptwusuopu大神的腳步，最近在研習動態(tài)規(guī)劃。動態(tài)規(guī)劃應(yīng)該叫一種解決問題的思想，記得又一次去某公司面試就被問到了這個。 多于動態(tài)規(guī)劃的理解，大致是這樣的，從空集合開始，每增加一個元素就求它的最優(yōu)解，直到所有元素加進來，就得到了總的最優(yōu)解。 比較典型的應(yīng)用就是背包問題，有一個重量一定的包，有若干件物品，他們各自有不同的重量和價值，怎樣背才能取得最大價值。 錯誤的理解：去價值/重量比最大的物品多裝（之前我也是這么想的，但是在背包重量一定的情況下這么做并不合理，范例很容易想到）

2.題目

要實現(xiàn)的題目是摘抄于另一位大神的博客，講的很好，可惜不是java實現(xiàn)的，有興趣可以看下面的引用。

題目描述：

有編號分別為a,b,c,d,e的五件物品，它們的重量分別是2,2,6,5,4，它們的價值分別是6,3,5,4,6，現(xiàn)在給你個承重為10的背包，如何讓背包里裝入的物品具有最大的價值總和？

name	weight	value	1	2	3	4	5	6	7	8	9	10
a	2	6	0	6	6	9	9	12	12	15	15	15
b	2	3	0	3	3	6	6	9	9	9	10	11
c	6	5	0	0	0	6	6	6	6	6	10	11
d	5	4	0	0	0	6	6	6	6	6	10	10
e	4	6	0	0	0	6	6	6	6	6	6	6

3.代碼實現(xiàn)

public class Main {public static void main(String[] args) {// TODO Auto-generated method stub final int packageWheight=10;//包的重量Package[] pg={new Package(6,2,"a"),new Package(3,2,"b"),new Package(5,6,"c"),new Package(4,5,"d"),new Package(6,4,"e") };int[][] bestValues = new int[pg.length+1][packageWheight+1];for(int i=0;i<=pg.length;i++){for(int j=0;j<=packageWheight;j++){if(i==0||j==0){bestValues[i][j]=0;//臨界情況}else{if(j<pg[i-1].getWheight()){bestValues[i][j] = bestValues[i-1][j];//當?shù)趎件物品重量大于包的重量時，最佳值取前n-1件的}else{int iweight = pg[i-1].getWheight(); //當?shù)趎件物品重量小于包的重量時，分兩種情況，分別是裝第n件或不裝，比較取最大int ivalue = pg[i-1].getValue(); bestValues[i][j] = Math.max(bestValues[i-1][j], ivalue + bestValues[i-1][j-iweight]); }}}}System.out.print(""+bestValues[pg.length][packageWheight]);}}public class Package {int value;int wheight;String name;Package(int value,int wheight,String name){this.value=value;this.wheight=wheight;this.name=name;}public int getWheight(){return wheight;}public int getValue(){return value;}public String getName(){return name;} }

有興趣的同學(xué)可以到我的github去clone這個工程：https://github.com/jimenbian/DynamicPrograme
引用：【1】http://blog.csdn.net/mu399/article/details/7722810
? ? ? ? ? ?【2】http://www.cnblogs.com/SDJL/archive/2008/08/22/1274312.html ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【3】http://blog.163.com/guixl_001/blog/static/41764104200863015855721/

/********************************

* 本文來自博客 ?“李博Garvin“

* 轉(zhuǎn)載請標明出處:http://blog.csdn.net/buptgshengod

******************************************/

總結(jié)

以上是生活随笔為你收集整理的【算法数据结构Java实现】Java实现动态规划（背包问题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。