java 中的 0/1 个背包

Question

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

Answer 1

你的电话应该是这样的：

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 Knapsack 是一种 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。

java 中的 0/1 个背包

0/1Knapsack in java

java

knapsack-problem