问题描述：
小偷深夜潜入一家珠宝店，店里有5件宝物，重量分别为W{1,3,2,4,5}，对应的价值为V{200,100,300,150,350 }。小偷随身只携带了一个容量为5的背包，问小偷应如何选择才能使偷得宝物的价值最大？
解题思路：
一、建立动态规划数组dp[i][j]，表示小偷在背包总容量为j且只有前i件宝物可供选择的情况下能带走的最大价值；
二、小偷将宝物一件一件的往袋子里装，对于每件物品i：小偷首先需要考虑，携带的容量为j的包有可能装的下这件宝物i吗？换句话说，小偷除了宝物i以外其他宝物都不带走，他的包能不能装下，即j>=w[i]是否成立？
（1）如果条件j>=w[i]不成立，那么说明这件宝物i小偷无论如何也带不走了，此时他的能带走的最大价值dp[i][j]=dp[i-1][j];
（2）如果条件j>=w[i]成立，即小偷是有能力带走这件宝物的，但这个狡猾的小偷又要思考了，宝物i我到底要不要拿走呢？如何取舍才能使得我背包的宝物总价值最大呢？
i：如果小偷选择不取宝物i，那么此时背包的总价值与只有前i-1件宝物可选择且背包总容量为j时能获得的最大价值是一样的，即dp[i][j]=dp[i-1][j]；
ii：如果小偷选择宝物i，那么此时背包的总价值为只有前i-1件宝物可选择且背包总容量为j-w[i]时能获得的最大价值再加上宝物i的价值v[i]，即dp[i][j]=dp[i-1][j-w[i]]+v[i];
二者选择总价值最大的即可，接下来我们就按此思路撸代码了......
Java代码实现：
public class Main {
public static void main(String[] args) {
int totalWeight=5;//背包容量
Treasure[] packages={new Treasure(200, 1),
new Treasure(100, 3),
new Treasure(300, 2),
new Treasure(150, 4),
new Treasure(350, 5)};
System.out.println(solution(packages, totalWeight));
}
public static int solution(Treasure[] treasures,int bagCapacity){
int maxValue=-1;
if(treasures==null||treasures.length==0||bagCapacity<=0){//参数合法性检查
maxValue=0;
}else {
int treasuresNum=treasures.length;
//定义动态规划数组dp[i][j],记录有前i件物品可供选择且背包容量为j时理科获得的最大价值
//这里加1是因为考虑了可选择宝物数为0和背包容量为0的情况
int dp[][]=new int[treasuresNum+1][bagCapacity+1];
//初始化可选择宝物数为0或者背包容量为0的情况,这个初始化可省略,数组定义时即自动初始化为0了
for(int i=0;i<treasuresNum;i++){
dp[i][0]=0;
dp[0][i]=0;
}
//开始动态规划，由下而上
int currentValue=0;
int currentWeight=0;
for(int i=1;i<=treasuresNum;i++){
currentValue=treasures[i-1].getValue();//注意这里要减1
currentWeight=treasures[i-1].getWeight();
for(int j=1;j<=bagCapacity;j++){
if(currentWeight>j){//当前考虑的宝物重量超过了背包最大容量
dp[i][j]=dp[i-1][j];
}else {//反之，小偷有能力带走这块宝物，但他需要考虑下是否价值最大
dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-currentWeight]+currentValue);
}
}
}
maxValue=dp[treasuresNum][bagCapacity];
}
return maxValue;
}
}
class Treasure{
private int value;//价值
private int weight;//重量
public Treasure(int value,int weight) {
this.setValue(value);
this.setWeight(weight);
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
}
复杂度分析
以上方法的时间和空间复杂度均为O(VN)，其中时间复杂度以不可再优化，但空间复杂度还有在优化的空间，优化解法见参见我的另一篇博文背包问题系列之--01背包空间优化解法
总结
动态规划现在是编程面试中的热门，如果面试题是求一个问题的最优解(通常是求最大值或者最小值)，而且该问题可分解成若干个子问题，并且子问题之间还有重叠的更小子问题，那么我们就可考虑使用动态规划来解决这个问题了。
