java - Java中的0/1背包

我目前无法找到该程序在做什么错。特别要求我遵循给出的指示，例如使用double 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));
    }
}

最佳答案

您的呼叫应如下所示：

m(i - 1, weightLimit, w)

代替

m(i,weightLimit,w)

当您使用m（i，weightLimit，w）进行调用时，在m（）中i不小于或等于0，因此它正在尝试访问w [i]。但是第i个索引在i的数组大小中不存在。我们只能访问数组的第0至第（i-1）个索引。

注意：0/1背包是一种dp算法，其中必须为递归dp提供记忆。但是您尚未这样做。同样，在您的基本情况下，当i = 0时您将返回。但是您不能这样做。因为采用0指数权重也可以使您获得最大权重。