Java中2组的最近和 [英] Closest Sums of 2 groups in java

问题描述

我在解决此问题时遇到了一些问题:

I'm having some problems solving this question:

给定一个 int s数组，将输入分为两组，使它们的总和尽可能接近，这两组的长度必须相等，或者如果输入的长度为奇数，则一组可以比另一组多.然后先打印较低的金额，然后打印较高的金额.

Given an array of ints, divide the input into 2 groups such that their sums are as close as possible, the 2 groups must be equal in length, or if the input is odd length then one group can have 1 more than the other. Then print the lower sum first, and the higher sum after.

例如:输入-> [4,6,17,3,2,5,10] 输出-> 23,24([17,5,2]，[10,6,4,3])

Ex: input -> [4,6,17,3,2,5,10] output -> 23,24 ([17,5,2] , [10,6,4,3])

这是我想出的，到目前为止，我已经测试了它通过了，但是我不知道它是否正确:

This is what I've come up with and so far what I've tested it's passed but I do not know if it's actually correct:

public static String closestSums(int[] input) {
    Integer sum1 = 0;
    Integer sum2 = 0;
    Integer dif = 0;
    Integer bigSum = 0;

    List<Integer> list = new ArrayList<>();
    List<Integer> list1 = new ArrayList<>();
    List<Integer> list2 = new ArrayList<>();

    for (int x = 0; x < input.length; x++) {
        list.add(input[x]);
    }

    Collections.sort(list);

    for (int x = list.size(); x >= 0; x--) {
        bigSum += list.get(x);
        if (dif == 0) {
            dif = list.get(x);
            list2.add(list.get(x));
        }
        else if (dif > 0) {
            dif -= list.get(x);
            list1.add(list.get(x));
        }
        else {
            dif += list.get(x);
            list2.add(list.get(x));
        }
    }

    dif = Math.abs(dif);
    if (dif != 0) {
        sum2 = (bigSum / 2) + dif;
        sum1 = bigSum / 2;
    }
    else {
        sum2 = bigSum / 2;
        sum1 = bigSum / 2;
    }
    return sum1 + ", " + sum2;
}

推荐答案

不正确.

不管另一个答案中提到的一堆小小的编码错误，您的算法都不起作用.

Regardless of the bunch of small coding mistakes that are mentioned in the other answer, your algorithm doesn't work.

考虑输入 [3、3、2、2、2] .您的算法会将其分为 [3，2，2] 和 [3，2] ，其差为 7-5 = 2 .但是，存在更好的等分总和: [3，3] 和 [2，2，2] .

Consider the input [3, 3, 2, 2, 2]. Your algorithm will divide it into [3, 2, 2] and [3, 2] with a difference of 7-5=2. However, a better split with equal sums exists: [3, 3] and [2, 2, 2].

我不会提供完整的算法，但会给您一些提示:

I am not going to provide a complete algorithm but give you a few hints:

1-最小差异可以进行二进制搜索.如果您能提出一种算法，该算法决定是否可以拆分数组，以便对于给定的 d ，片段总和的差最大为 d ，那么您可以对算法输出 1 的最小 d 进行二进制搜索.

1 - The minimum difference can be binary-searched. If you can come up with an algorithm that decides whether it is possible to split the array so that the difference of the sums of the pieces is at most d for a given d, then you can binary search the minimum d for which the algorithm outputs 1.

2-查看子集总和问题，它可以帮助解决我定义的子问题在项目1中.

2 - Look at the subset sum problem, it can help with the subproblem I defined in item 1.

这篇关于Java中2组的最近和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！