gpt4 book ai didi

java - Java 中的 0/1 背包

转载 作者:行者123 更新时间:2023-11-30 10:06:38 27 4
gpt4 key购买 nike

我目前无法找到我在这个程序中做错了什么。我被特别要求遵循给出的指示,例如使用 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 Knapsack 是一种 dp 算法,其中递归 dp 必须内存。但是你没有这样做。此外,在您的基本情况下,您将在 i = 0 时返回。但是您不能这样做。因为取0指标权重也可以给你最大权重。

关于java - Java 中的 0/1 背包,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54566354/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com