问题描述：

    小偷深夜潜入一家珠宝店，店里有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背包空间优化解法

总结

    动态规划现在是编程面试中的热门，如果面试题是求一个问题的最优解(通常是求最大值或者最小值)，而且该问题可分解成若干个子问题，并且子问题之间还有重叠的更小子问题，那么我们就可考虑使用动态规划来解决这个问题了。