找到最佳子数组和并返回它和子数组

Question

我对 Java 和编码都比较陌生，目前正在尝试解决一个子集问题。

目标是让用户输入数字的数量，然后输入每个数字直到指定的数量，计算机相应地要求每第 n 个数字。

之后计算机要计算所有子集的总和，return最接近pi的子集，以及同一行内[x,y,z]这种形式的子集
我很好地管理了第一部分，尽管为了方便起见可能已经使用开关盒对其进行了改进。它将输入数字添加到数组

但是我在解决这个问题的第二部分，我不知道如何 progress/arrange 代码以使其输出所需的结果。我得到的建议是，一个包含 n 个元素的集合的 for 循环：

for a from 0 to 2^n
 for i from 0 to n
  when the binary representation of x on has a 1 at the i-th position
   add data[i] to solution.

这应该可以找到数组的所有子集。之后我应该添加每个元素，检查与 pi 的距离是否减小并将元素添加到解决方案集中。或者至少这是目标，但我的代码不起作用，因为我不知道从哪里开始安排它。我也不知道用什么初始化 bestsum，或者二进制表示算法如何工作，或者如何按顺序将元素添加到解决方案数组。编辑：我取得了进展，下面的代码输出了所有的子数组，并且它正确地计算了最接近的总和，但我不知道如何 'save' 最好的子数组（总和最接近的子数组）以便我可以输出它最后加上总和。我很新，所以我还没有学习过列表甚至方法，但是这本书的这一章有这个问题，我想用建议的方法和可能只用简单的循环来解决它。

public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("How many numbers should be read? ");
        int count = input.nextInt();
        double[] data = new double[count];
        double [] solution = new double[count];
        double bestsum = 0.0;     
       


        for (int i = 0; i < count; i++) {
            if ((i + 1) % 10 == 1) {
                System.out.println("Enter " + (i + 1) + "st number: ");
                data[i] = input.nextDouble();
            } else if ((i + 1) % 10 == 2) {
                System.out.println("Enter " + (i + 1) + "nd number: ");
                data[i] = input.nextDouble();
            } else if ((i + 1) % 10 == 3) {
                System.out.println("Enter " + (i + 1) + "rd number: ");
                data[i] = input.nextDouble();
            } else {
                System.out.println("Enter " + (i + 1) + "th number: ");
                data[i] = input.nextDouble();
            }
        }
        for (int j = 0; j <(1 << count); j++) {
            System.out.print("{ ");
            double sum = 0.0;
            for (int x = 0; x < count; x++) {
                if ((j & (1 << x)) > 0) {
                    System.out.print(data[x] + " ");
                    sum = sum + data[x];
                }
                solution[x] = data[x];
            }


            System.out.println("}");
            if (Math.abs(sum - Math.PI) < Math.abs(bestsum - Math.PI)) {
                bestsum = sum;
            }
        }



System.out.println(bestsum);
        System.out.println(Arrays.toString(solution));

        }

    }

Answer 1

这是我解决这个问题的方法。

public static void main(String[] args) {
    
    Scanner input = new Scanner(System.in);
    System.out.println("How many numbers should be read? ");
    int count = input.nextInt();
    Double data[] = new Double[count];
    Double bestsum = 0.0;
    List<Double> bestArray= Collections.emptyList();
    Set<List<Double>> possibleArrays = new LinkedHashSet<>();
    


    for (int i = 0; i < count; i++) {
        if (i == 0) {
            System.out.println("Enter " + (i+1) + "st number: ");
            data[i] = input.nextDouble();
        } else if (i == 1) {
            System.out.println("Enter " + (i+1) + "nd number: ");
            data[i] = input.nextDouble();
        } else if (i == 2) {
            System.out.println("Enter " + (i+1) + "rd number: ");
            data[i] = input.nextDouble();
        } else {
            System.out.println("Enter " + (i+1) + "th number: ");
            data[i] = input.nextDouble();
        }

    }
    input.close();
    for (int i = 0; i < (1<<count); i++)
    {
        int m = 1; // m is used to check set bit in binary representation.
        List<Double> currentArray = new ArrayList<>();
        for (int j = 0; j < count; j++)
        {
            if ((i & m) > 0)
            {       
                currentArray.add(data[j]);
            }
            m = m << 1;
        }
        possibleArrays.add(currentArray);
    }
    Iterator<List<Double>> iterator = possibleArrays.iterator();
    iterator.next();
    for (int i = 1; i < possibleArrays.size(); i++) {
        Double sum=0.0;
        List<Double> currentArray = iterator.next();
        sum = currentArray.stream().collect(Collectors.summingDouble(Double::doubleValue));
        if(Math.abs(sum-Math.PI)<Math.abs(bestsum-Math.PI)) {
            bestArray = currentArray;
            bestsum = sum;
        }
        
    }

    System.out.println("possibleArrays: " + possibleArrays);
    System.out.println("solution: " + bestArray);
    System.out.println("bestsum: " + bestsum);

}

找到最佳子数组和并返回它和子数组

Finding best subarray sum and returning it and the subarray

java

arrays

subset