动态规划(5)----0-1背包

　　0-1背包是最基础的背包，一般题目描述为：给定m个物品，其中每个物品的重量用向量W描述，即第一个物品的重量为w1，物品的价值用向量V描述，另外给定一个容量为C的背包，问这个背包中能装下的物品的最大值为多少？

　　在这个问题中，有一个显著的特点就是每个物品只能用一次。那么我们分析分析这个问题，在分析问题的时候，为了方便明了，我们假设现在进行到了最后一步（这也是传说中的自顶向下的分析方法），我们假设存在这么一个函数F(n,C) 表示前n个物品放入到容量为C的背包中(这个背包刚好装满)所能获得到最大价值，当我们面对最后一个物品时，我们有两个选择：

　　1、将第n个物品丢弃，那么此时就用的最大价值为F(n-1, C)。这个很好理解，第n个丢了嘛，所以不算重量也不算价值。

　　2、将第n个物品放入，那么此时的最大价值是Vn+F(n-1, C-Wn)。这个式子也很好理解，Vn表示第n个物品的价值，后面的函数则表征前n-1个物品的价值。可能有同学无法理解背包容量为什么变成了C-Wn，这是因为背包的容量就是C，目前已经装满了，要想将第n个物品放进去，就必须腾出相应的空间，否则第n个物品放不进去。

　　在这两个选择下，我们选择受益最大的那个，因此存在一下的递推关系：F(n,C) = max(F(n-1,C), Vn+F(n-1, C-Wn))。

　　依据上述的递推关系，存在两种实现方式，首先就是动态规划，此外，动态规划可以转换成递归，因此存在两种编码方式。

　　首先我们看递归的方式

public int backpack(int[] value, int[] weight, int index, int C){
        /*结束条件*/
        if(index<0 || C<=0)
            return 0;

        /*不放第Index物品*/
        int ans = backpack(value, weight, index-1, C);
        /*放第Index个物品*/
        if(weight[index]<=C){
            ans = Math.max(ans,value[index]+backpack(value, weight, index-1, C-weight[index]));
        }
        /*先算不放的情况，因为不确定是容量是否够，在确定能放进去的情况下，算哪个更优*/
        return ans;
    }

　　其次我们看看动态规划的方式

public int backpackDP(int[] value, int[] weight, int C){
        int[][] dp = new int[value.length][C+1];
        /*容量为0的情况当然是什么都放不下去*/
        for(int i =0;i<value.length;++i)
            dp[i][0] = 0;

        for(int i =1;i<value.length;++i){
            /*外层是item, 内层是容量*/
            for(int j=0; j<C;++j){
                /*不放*/
                dp[i][j] = dp[i-1][j];
                if(weight[i]<=j){
                    dp[i][j] = Math.max(dp[i][j], value[i]+dp[i-1][j-weight[i]]);
                }
            }
        }
        return dp[value.length-1][C];
    }

　　两者的代码时很像的，但是，递归明显的计算次数比动态规划多。