0/1背包在Java

Question

我目前很难找到什么我做错了这个计划。我特别要求遵循给定的，例如使用双I，weightLimit，[] W上的方向;

我不断收到ArrayIndexOutOfBoundsException异常：6以及问题上线53和39

它是什么，我没有做是否正确？

import java.util.Scanner;

public class RecursiveKnapsack {

    static double max(double a, double b) {
        if (a > b)
            return a;
        else return b;
    }

    public static double m (int i,  double weightLimit,  double [] w) {
        if(i <= 0 || weightLimit == 0) 
            return 0;
        else if (w[i] > weightLimit) 
            return m(i-1,weightLimit,w);    
        else return  max(m(i-1, weightLimit, w),w[i] + m(i-1, weightLimit-w[i], w));

    }


    public static void main (String[]args) {

        Scanner input = new Scanner(System.in);

        //NumberofItems
        System.out.println("Enter the number of items: ");

        int i = input.nextInt();

        //Weight of Items
        System.out.println("Enter the weights for each item: ");

        double[] w = new double[i];

        //Inserting input in array
        for (int x=0; x < i; x++){
            w[x] = input.nextDouble();
        }

        //Limit
        System.out.println("Enter the weight limit for the bag: ");
        double weightLimit = input.nextDouble();

        System.out.println("The maximum weight of the items placed in the bag is " + m(i,weightLimit,w));   
    }
}

Answer 1

您的电话应该是这样的：

m(i - 1, weightLimit, w)

代替

m(i,weightLimit,w)

当你与米调用（I，weightLimit，W），以m（）i不小于或等于0，所以它试图访问W [i]中。但是，第i个指标并不在我的数组大小存在。我们可以第一个数组的索引只有0访问（I-1）。

注：0/1背包是一个DP算法，其中记忆化是必须的递归DP。可是你有没有这样做。此外，在你的基本情况你当i = 0。但是，你不能这样做回来。因为服用0指标的权重也可以给你的最大重量。

Answer 2

我同意@ mukit09的答案。只是多一点在这里澄清它。

你所得到的错误，因为你正在使用的阵列，即double w[]是大小i为您已声明。因此，阵列w的起始索引是0并用i-1结束。

但是，如果你在这条线检查：else if (w[i] > weightLimit)，它正试图获得在w[i]值，而实际上w[i-1]是它的最后一个索引。因此，它给你的ArrayIndexOutOfBounds Exception。