1.背景
追随着buptwusuopu大神的脚步，最近在研习动态规划。动态规划应该叫一种解决问题的思想，记得又一次去某公司面试就被问到了这个。
多于动态规划的理解，大致是这样的，从空集合开始，每增加一个元素就求它的最优解，直到所有元素加进来，就得到了总的最优解。
比较典型的应用就是背包问题，有一个重量一定的包，有若干件物品，他们各自有不同的重量和价值，怎样背才能取得最大价值。
错误的理解：去价值/重量比最大的物品多装（之前我也是这么想的，但是在背包重量一定的情况下这么做并不合理，范例很容易想到）
2.题目
要实现的题目是摘抄于另一位大神的博客，讲的很好，可惜不是java实现的，有兴趣可以看下面的引用。
题目描述：
有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为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.代码实现
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];//当第n件物品重量大于包的重量时，最佳值取前n-1件的
}
else{
int iweight = pg[i-1].getWheight(); //当第n件物品重量小于包的重量时，分两种情况，分别是装第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;
}
}
有兴趣的同学可以到我的github去clone这个工程：https://github.com/jimenbian/DynamicPrograme
/********************************
* 本文来自博客 “李博Garvin“
* 转载请标明出处:http://blog.csdn.net/buptgshengod
******************************************/
