0-1背包问题（递归，记忆化搜索，动态规划）

这道题我刚开始分析的时候主要是分不清楚这道题的重叠子问题在哪里，后来想明白了，我纠结在了选择放与不放第i个物品，背包的容量都不一样，怎么会有重叠子问题，但是，后来举了一些例子，发现处理[0,i]的物品对于背包此时的容量C，也是有重叠子问题的，即C也可能会相等，不过这个问题确实点。。。。。。，当然这个问题也是具有最优子结构的特性的，因为对于[0,n]个物品和背包容量为M，它的最大收益就取决于子问题[0,n-1]个物品，背包容量为M和[0,n-1]个物品，背包容量为M-weight[n]这两者中的最大值，分析了这两点之后，就可以了使用动态规划或者记忆化搜索来解决这个问题了

//0-1背包问题，无需事先排序
/*
已知条件：
1，背包容量M
2，各个物体的重量
3，各个物体的价值
 */
public class BagDongTai {
    //递归的写法
    //时间复杂度O(2^n)
    //空间复杂度O(1)
    //这个函数考虑的是[0,index]的物品放入容量为M（随时变化的）的背包中所获得的最大的收益
    private int findMax1(int[]W,int[]P,int M,int index){
        if(index<0){
            return 0;
        }//如果index的值不合法，返回0就可以了，因为[0,index]这个区间是没有物品的

        if(M<W[index]){
            return findMax1(W,P,M,index-1);
        }//如果当前的背包容量的值M是小于要放入的这个物品的重量的，那么就不能放入这个物品，就要看前一个物品

        //如果不是上面的这种情况的话，对于第index个物体，就有两种情况，一种是放，另一种是不放，故对应的递归的方程为
        return Math.max(findMax1(W,P,M,index-1),findMax1(W,P,M-W[index],index-1)+P[index]);
        //返回这两种情况的较大的值就可以了
    }
    public int MaxPro1(int[]W,int[]P,int M){
        int n=W.length;
        if(n==0||M==0){
            return 0;
        }//如果有0个物品或者背包容量为0，返回0就可以了
        return findMax1(W,P,M,n-1);
    }
    //记忆化搜索
    //时间复杂度O(n*C)n为物体的数量，C为背包的容积
    //空间复杂度O(n*C）
    private int[][]memo;//声明一个数组memo用于存储对于第index个物体（放或者不放），背包容量为M（是此时的）的最大的收益
    private int findMax2(int[]W,int[]P,int M,int index){
        if(index<0){
            return 0;
        }//如果index的值不合法，返回0就可以了，因为[0,index]这个区间是没有物品的

        if(M<W[index]){
            return findMax2(W,P,M,index-1);
        }//如果当前的背包容量的值M是小于要放入的这个物品的重量的，那么就不能放入这个物品，就要看前一个物品

        if(memo[index][M]!=-1){
            return memo[index][M];
        }//如果memo中有存储的这个情况的最大的收益，返回就可以了

        //如果不是上面的这种情况的话，对于第index个物体，就有两种情况，一种是放，另一种是不放，故对应的递归的方程为
        int cur= Math.max(findMax2(W,P,M,index-1),findMax2(W,P,M-W[index],index-1)+P[index]);
        memo[index][M]=cur;//将最大的收益存储到memo中
        //返回这两种情况的较大的值就可以了
        return cur;
    }
    public int MaxPro2(int[]W,int[]P,int M){
        int n=W.length;
        if(n==0||M==0){
            return 0;
        }//如果有0个物品或者背包容量为0，返回0就可以了
        memo=new int[n][M+1];
        for(int i=0;i<n;i++){
            Arrays.fill(memo[i],-1);
        }//初始化memo数组
        return findMax2(W,P,M,n-1);
    }
    //动态规划的写法
    //时间复杂度O(n*C)n为物体的数量，C为背包的容积
    //空间复杂度O(n*C）
    public int MaxPro3(int[]W,int[]P,int M){
        int n=W.length;
        if(n==0||M==0){
            return 0;
        }//如果物品的数量为0或者背包的容量为0的话，返回最大收益0就可以了
        int memo[][]=new int[n][M+1];//声明一个数组，用来存储[0，i]的物品，背包容量为j所对应的最大的收益
        for(int i=0;i<n;i++){
            for(int j=0;j<=M;j++){
                if(W[i]>j){
                    memo[i][j]=(i-1)<0?0:memo[i-1][j];//这里要防止-1越界
                }//如果当前物品的重量大于背包容量j，那么它的最大收益就等于前一个物品在背包容量为j时的最大的收益
            /*
            否则的话，对一个物体index，就有两种情况，一种是不放入这个物品，那此时的index个物品，背包容量为j的情况的最大的收益与index-1
            个物体，背包容量为j的最大收益相同，另一种是放入这个物体，那么[0,index]的物体对应的最大的收益为[0,index-1]的物体对于容量为
            j-index的物体的重量的最大的收益，在这两者中寻找一个最大值，记录到memo中
             */
                else{
                memo[i][j]=Math.max((i-1)<0?0:memo[i-1][j],(i-1<0?0:memo[i-1][j-W[i]])+P[i]);
                }
            }
        }
        return memo[n-1][M];
    }
public static void main(String[]args){
    int[]W={2,3,4,5};
    int[]P={1,2,5,6};
 System.out.println(new BagDongTai().MaxPro3(W,P,7));
}
}