时间戳

首页 > 解决方案 > java中2组的最接近总和

java - java中2组的最接近总和

问题描述

我在解决这个问题时遇到了一些问题：

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

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

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

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;
}

标签： javaalgorithm

解决方案

这是不正确的。

不管其他答案中提到了一堆小的编码错误，您的算法都不起作用。

考虑输入[3, 3, 2, 2, 2]。您的算法会将其划分[3, 2, 2]为. 但是，存在更好的等和分割：和。[3, 2]7-5=2[3, 3][2, 2, 2]

我不会提供一个完整的算法，但给你一些提示：

1 - 可以对最小差异进行二分搜索。如果您能想出一个算法来决定是否可以拆分数组，以便在d给定的情况下，各部分的总和之差最多，那么您可以对算法输出d的最小值进行二分法搜索。d1

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

推荐阅读