Leetcode刷题之一口气看完01背包和完全背包的一维数组版以及二维数组版

01背包二维数组

• 无遍历顺序要求
• 可先遍历物品再重量，也可先重量再物品；但先物品较好理解

   //二维数组的01背包
    public static void getValue(int W,int[] weight,int[]value) {
        int N=value.length;
        int dp[][]= new int[N+1][W+1];//dp[i][j]意思是：背包容量为j时，在前i件物品中取小于等于i件物品，此时取得的物品的价值最大
        //注意下标问题
        for(int i=1;i<=N;i++) {
            for(int j=0;j<=W;j++) {
                if(weight[i-1]>j) {//太重了，拿不了
                    dp[i][j]=dp[i-1][j];
                }else {//拿：dp[i-1][j-weight[i]]+value[i]   不拿： dp[i-1][j]
                    dp[i][j]=Math.max(dp[i-1][j-weight[i-1]]+value[i-1], dp[i-1][j]);
                }
            }
        }

        System.out.println(dp[N][W]);
    }

    @Test
    public void test1(){
        int W=20;//背包容量为20
        int[] weight = {2, 3, 4, 5, 9};//重量 2 3 4 5 9
        int[] value = {3, 4, 5, 8, 10};//价值3 4 5 8 10
        getValue(W,weight,value);//26
    }

01背包一维数组版

• 一定要先遍历物品再遍历背包容量，且背包容量为倒序
• 因为如果背包容量为正序就代表可以多次拿同一物品，所以倒序限制每次只拿一个
• 正因为限制每次只拿一个所以不能将其放在外层循环，因此一定要先遍历物品

//一维数组（滚动数组）01背包
    //注意01背包一维版遍历一定要先遍历物品再遍历背包容量，且背包容量为倒序
    public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
        int wLen = weight.length;
        //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
        int[] dp = new int[bagWeight + 1];
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 0; i < wLen; i++){
            for (int j = bagWeight; j >= weight[i]; j--){//且为倒序
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }

        System.out.println(dp[bagWeight]);
    }

    @Test
    public void test2() {
        int[] weight = {2, 3, 4, 5, 9};//重量 2 3 4 5 9
        int[] value = {3, 4, 5, 8, 10};//价值3 4 5 8 10
        int bagWight = 20;
        testWeightBagProblem(weight, value, bagWight);
    }

完全背包一维数组版

• 每件物品都有无限个（也就是可以放入背包多次）
• 可以先物品后重量，也可以先重要后物品；但注意遍历重要要正序（和01区分）

 //完全背包一维版-先遍历物品再遍历背包
    public static void testWeightBagProblem3(int[] weight, int[] value, int bagWeight){
        int wLen = weight.length;
        //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
        int[] dp = new int[bagWeight + 1];
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 0; i < wLen; i++){
            for (int j = weight[i]; j <=bagWeight; j++){//且为倒序
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }

        System.out.println(dp[bagWeight]);
    }

    @Test
    public void test3() {
        int[] weight = {2, 3, 4, 5, 9};//重量 2 3 4 5 9
        int[] value = {3, 4, 5, 8, 10};//价值3 4 5 8 10
        int bagWight = 20;
        testWeightBagProblem3(weight, value, bagWight);//32
    }

//完全背包一维版--先遍历背包再遍历物品
    @Test
    public void testCompletePackAnotherWay(){
        int[] weight = {2, 3, 4, 5, 9};
        int[] value = {3, 4, 5, 8, 10};
        int bagWeight = 20;
        int[] dp = new int[bagWeight + 1];
        for (int i = 1; i <= bagWeight; i++){ // 遍历背包容量
            for (int j = 0; j < weight.length; j++){ // 遍历物品
                if (i - weight[j] >= 0){
                    dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
                }
            }
        }
        for (int maxValue : dp){
            System.out.println(maxValue + "   ");
        }
    }