【基础算法复习】01背包问题（一）

一、绪论

　　01背包问题是一个经典的动态规划问题，问题描述为“有n个物品，其价值分别为v[n],要求将其装在承重为m的背包，每个物品只能装一次的情况下，在不超过承重的范围下价值最大”。从这个题目中可以看出，01背包的特点就是：每种物品仅有一件，可以选择放或不放。当一个问题的局部变化很明显的时候，考虑动态规划的解决方案，即找出状态方程。

　　在01背包问题中，其状态转移方程是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}.

二、目的

　　找出状态方程后，可以根据状态方程得出这个问题的两个状态：

　　当前物品i，weight[i] > j，那么maxValue[i][j] = maxValue[i-1][j] ;

　　当前物品i，weight[i]<=j，那么maxValue[i][j] = max{maxValue[i-1][j],maxValue[i-1][j-weight[i]]+value[i]} ;

三、编程实现

　　代码如下：

     int bag = 0;
        int[] weight = {5,3,6,2,3} ;
        int[] value = {1,3,2,1,3} ;
        for(int i:weight ) {
            bag = bag + i;
        }
        bag= bag/2 ;
        int[][] maxValue =new int[6][10] ;

        for(int i =0;i<6;i++){
            for(int j=0;j<10;j++) {
                if (i == 0 || j == 0)
                    maxValue[i][j] = 0;
                else{
                    if(weight[i-1] > j){
                        maxValue[i][j] = maxValue[i-1][j] ;
                        
                    }else{
                        maxValue[i][j] = Math.max(maxValue[i-1][j], maxValue[i-1][j-weight[i-1]]+value[i-1]) ;
                       
                    }
                }
            }
        }

        for (int i = 1; i <6; i++) {
            for (int j = 1; j <10; j++) {
                System.out.print(maxValue[i][j]+"	");
                if(j==bag){
                    System.out.println();
                }
            }
        }
    }

四、优化

　　在上述代码中，使用了二维数组来进行计算最佳的价值，在时间复杂度上不能优化，但是从空间上还有优化的空间。使用一维数组并且逆序遍历，也是可以实现找出上一个状态和下一个状态之间的联系。

 int[] best=new int[11] ;
        System.out.println("best[10]="+best[10]);

        for(int i =0;i<5;i++){
            for(int j=10;j>=weight[i];j--) {
                best[j]=Math.max(best[j],best[j-weight[i]]+value[i]);
                System.out.println("best["+j+"]="+best[j]+"	");
            }
        }