0-1背包问题-例题

题目摘自《卡码网》46题

题意理解

????????m种材料——对应m物品

????????大小问n的行李箱——对应大小为n的背包

? ? ? ? 所以该问题是一个0-1背包问题，采用动态规划的一般思路来解题。

解题思路：

? ? ? ? 动规五部曲：

? ? ? ? （1）定义二维dp数组，明确dp[i][j]的定义

? ? ? ? ? ? ? ? dp[i][j]表示编号在[0,i]的物品任取，放入大小为j的背包内，所得的最大价值

? ? ? ? （2）递推公式：

? ? ? ? ? ? ? ? dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+values[i])

? ? ? ? （3）初始化：根据递推公式可以看出，总是由左边和上边推导当前的数值，所以初始化第一行第一列。

? ? ? ? （4）遍历顺序：先物品后背包，先背包后物品都可以，因为二维dp数组保留了两个维度所有值。

? ? ? ? （5）打印结果，debug.

1.二维dp数组解决0-1背包问题

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int m,n=0;
        m=sc.nextInt();
        n=sc.nextInt();
        int[] volumeArr=new int[m];
        int[] valuesArr=new int[m];
        for(int i=0;i<m;i++) volumeArr[i]=sc.nextInt();
        for(int i=0;i<m;i++) valuesArr[i]=sc.nextInt();
        Main obj=new Main();
        System.out.println(obj.sloveBagProblem(n,volumeArr,valuesArr));


    }


    public int sloveBagProblem(int bagSize,int[] volumeArr,int[] valuesArr){
        //定义dp数组
        int dp[][]=new int[volumeArr.length][bagSize+1];
        for (int i = 0; i <volumeArr.length; i++) {
            Arrays.fill(dp[i], -1);
        }
        //初始化-第一列:背包大小为0
        for(int i=0;i<valuesArr.length;i++) dp[i][0]=0;
        //初始化-第一行：能放入则放入
        for(int j=1;j<=bagSize;j++){
            if(volumeArr[0]>j){
                dp[0][j]=0;
            }else{
                dp[0][j]=valuesArr[0];
            }
        }
        //遍历：双for循环
        for(int i=1;i<volumeArr.length;i++){
            for(int j=1;j<=bagSize;j++){
                //判断是否能否加入
                if(volumeArr[i]>j){
                    //不能放入
                    dp[i][j]=dp[i-1][j];
                }else{
                    //能放入
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-volumeArr[i]]+valuesArr[i]);
                }
            }
        }
        return dp[volumeArr.length-1][bagSize];
    }
}

2.一维dp数组（一维动态滚动数组）解决0-1背包问题——存储压缩?

dp[j]表示背包大小为j时，任意取放物品能获得的最大价值。

递推公式：dp[j]=Math.max(dp[j],dp[j-volumeArr[i]]+valuesArr[i])

注意：前面的值会影响后面值的操作，所以在遍历背包大小时，从后往前操作，防止重复操作同一行数据，导致物品重复加入。

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int m,n=0;
        m=sc.nextInt();
        n=sc.nextInt();
        int[] volumeArr=new int[m];
        int[] valuesArr=new int[m];
        for(int i=0;i<m;i++) volumeArr[i]=sc.nextInt();
        for(int i=0;i<m;i++) valuesArr[i]=sc.nextInt();
        Main obj=new Main();
        System.out.println(obj.sloveBagProblem(n,volumeArr,valuesArr));


    }


     public int sloveBagProblem(int bagSize,int[] volumeArr,int[] valuesArr){
        //定义dp数组
        int dp[]=new int[bagSize+1];
        //初始化
        Arrays.fill(dp,0);
        //遍历：双for循环
        for(int i=0;i<volumeArr.length;i++){
            for(int j=bagSize;j>=0;j--){
                //判断是否能否加入
                if(volumeArr[i]<=j){
                    //能放入
                    dp[j]=Math.max(dp[j],dp[j-volumeArr[i]]+valuesArr[i]);
                }
            }
        }
        return dp[bagSize];
    }
}

?

3.分析

时间复杂度：

? ? ? ? O(m*n)

空间复杂度：

? ? ? ? 二维：O(m*n)

? ? ? ? 一维：O(n)