背包问题(0/1背包问题)（一维数组回滚解法和二维数组解法）_m0_57921272的博客

 1.（0,1）背包问题普通版(定义二维数组)采用动态规划

System.out.println("请输入背包容量和数量");
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt(); // 容量
int q=scanner.nextInt();  ///数量
int arr[]=new int[q+1];//存储重量
int brr[]=new int[q+1];//存储金额
arr[0]=0;
brr[0]=0;
int temp=1;
while(temp<=q){
    int c=scanner.nextInt(); // 重量
    int d=scanner.nextInt();  ///金额
    arr[temp]=c;
    brr[temp]=d;
    temp++;
}
int[][] max=new int[q+1][n+1];
for(int i=0;i<max.length;i++){
    for(int j=0;j<max[i].length;j++) {
        if (i == 0 || j == 0) {//初始化当容量为空或者物品为空最大金额为0
            max[i][j] = 0;
        } else {
            if (arr[i] > j) { //不能拿当前数值
                max[i][j] = max[i - 1][j];
            } else {
                //当可以拿时分为拿和不拿(取最大值)
                max[i][j] = Math.max((max[i - 1][j - arr[i]]) + brr[i], max[i - 1][j]);
            }
        }
    }
}
return max[q][n];

 2.（0,1）背包问题进化版(定义一维数组回滚)采用动态规划

System.out.println("请输入背包容量和数量");
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt(); // 容量
int q=scanner.nextInt();  ///数量
int arr[]=new int[q+1];//存储重量
int brr[]=new int[q+1];//存储金额
arr[0]=0;
brr[0]=0;
int temp=1;
while(temp<=q){
    int c=scanner.nextInt(); // 重量
    int d=scanner.nextInt();  ///金额
    arr[temp]=c;
    brr[temp]=d;
    temp++;
}
int[] max=new int[n+1];
for(int i=0;i<q+1;i++){
    //因为要用到上一列数组,所以要从后往前推防止覆盖
    for(int j=n;j>0;j--) {
        if (i == 0 || j == 0) {
            max[j] = 0;
        } else {
            if (arr[i] > j) { //不能拿当前数值
                max[j] = max[j];
            } else {
                //当可以拿时分为拿和不拿
                max[j] = Math.max((max[j - arr[i]]) + brr[i], max[j]);
            }
        }
    }
}
return max[n];