java - 使用递归和数组的背包解决方案

Question

我想知道修改此代码的最佳方法。我希望用户通过键盘输入不同的权重和容量，而不是将整数添加到代码本身的数组中。

现在我在插入数据时遇到编译错误。我认为问题出在 for 循环中。

import java.util.*;

public class NN01276494 {
  public static ArrayList <Double> sack = new ArrayList <Double> ();
public static void main(String [] args){
    Scanner in = new Scanner (System.in);
int i =0;
 for(i = 0; i<sack.length; i++){
 System.out.println("Enter Capacity");
 sack.size(in.nextDouble());
 }
while (in.hasNextDouble()){
System.out.print("Enter weights");
sack.add(in.nextDouble());
    i++;
}


}

public static Boolean knapsackproblem(double targetWeight, int index)
{
    Boolean complete = false;

    if(index == sack.size()) return false;
    if(sack.get(index) == targetWeight)
    {
        System.out.print("Answer: " + sack.get(index) + " ");
        complete = true;
    }; //DONE
    if(sack.get(index) < targetWeight) 
    {
        complete = knapsackproblem(targetWeight-sack.get(index), index+1);         
        if(complete) System.out.print(sack.get(index) + " ");
        for(int i = index+1; i < sack.size(); i++) 
        {
            if(!complete) complete = knapsackproblem(targetWeight, i);
        }
    }
    if(sack.get(index) > targetWeight) complete =   
    knapsackproblem(targetWeight, index+1);


    return complete;
}
}

Answer 1

在java中接受用户输入最常见的方式是Scanner类。这允许您的用户输入到控制台，并且您的程序可以使用他们的输入。 Here是详细介绍扫描仪的 javadoc，但您需要执行以下操作才能接受用户的整数输入:

首先，导入扫描仪字典以便您可以使用它。

import java.util.Scanner;

这将使您能够访问扫描仪库。要构建扫描器，您需要在声明中指定输入流。要使控制台成为输入流，请像这样声明它:

Scanner nameOfScanner = new Scanner(System.in);

现在，要获取数组的整数，请根据需要多次使用方法.nextInt()。确保分别询问用户每个输入，如果您希望用户能够控制数组的大小，您也可以询问用户。以防万一您不知道，您可以声明一个数组具有一定的大小，但直到稍后才指定每个位置中的内容，如下所示:

int[] nameOfArray = new int[sizeOfArray];

另外，我注意到在 knapsackproblem() 方法中间的 if 语句的右括号后面有一个分号。我不知道这是否是您的问题中的拼写错误或实际上是您的代码中的拼写错误，但它确实不应该存在。

我希望这对您有所帮助，祝您编码顺利!