如何将整数范围分成两个相等的部分

Question

我有一个像这样的整数数组

int [] num = {5, 8, 1, 1, 2, 3, 2}

我想把它分成2部分，这样2组的总数会尽可能相等：（输出）

SET 1: 5 Piece(s)
1
1
2
2
5
Total: 11

SET 2: 2 Piece(s)
8
3
Total: 11

另一个例子是

int [] num = {4, 6, 1, 2, 3, 3, 4}

输出如下：

SET 1: 3 Piece(s)
3
4
4
Total: 11

SET 2: 4 Piece(s) 
6
1
2
3
Total: 12

有什么帮助吗？ =) 谢谢

Answer 1

有一个 for 循环像这样循环：

int sum =0:
for(int I=0; I<num.length/2; I++){
System.out.println(num[i]);
sum=sum+num[i];
}
System.out.println(sum);

(写于ipad 如有错误请见谅。

Answer 2

如果数组不是太长，尝试一个懒惰的解决方案：暴力破解。由于您需要的只是将它分成两组，因此您需要检查 2^n 种可能性，因为一个数字要么在第一组中，要么不在（即在第二组中）。

这是我刚写的示例代码：

public static int[][] bruteForce(int[] input) {
    int n = input.length;
    int[][] res = new int[2][n];
    int minVal = Integer.MAX_VALUE;
    int iMinVal = 0;
    int limit = (int) Math.pow(2, n);

    for (int i = 0; i < limit; i++) {
        int v = i;
        int diff = 0;
        for (int j = 0; j < n; j++) {
            diff = diff + ((v & 1) == 0 ? +1 : -1) * input[j];
            v = v >> 1;
        }
        if (Math.abs(diff) < minVal) {
            iMinVal = i;
            minVal = Math.abs(diff);
        }
    }

    int a = 0, b = 0;
    for (int i = 0; i < n; i++) {
        if ((iMinVal & 1) == 0) {
            res[0][a++] = input[i];
        } else {
            res[1][b++] = input[i];
        }
        iMinVal = iMinVal >> 1;
    }

    return res;
}

public static void main(String[] args) {
    int[] num = {5 ,8 ,1 ,1 ,2 ,3 ,2};
    int[] num2 = {4, 6, 1, 2, 3, 3, 4};

    int[][] r = bruteForce(num);
    System.out.println("First example:");
    System.out.println(Arrays.toString(r[0])+ ", sum = "+Arrays.stream(r[0]).sum());
    System.out.println(Arrays.toString(r[1])+ ", sum = "+Arrays.stream(r[1]).sum());

    r = bruteForce(num2);
    System.out.println("Second example:");
    System.out.println(Arrays.toString(r[0])+ ", sum = "+Arrays.stream(r[0]).sum());
    System.out.println(Arrays.toString(r[1])+ ", sum = "+Arrays.stream(r[1]).sum());
}

输出：

First example:
[5, 1, 3, 2, 0, 0, 0], sum = 11
[8, 1, 2, 0, 0, 0, 0], sum = 11
Second example:
[2, 3, 3, 4, 0, 0, 0], sum = 12
[4, 6, 1, 0, 0, 0, 0], sum = 11

如果数组的长度很大，那么我想尝试一些智能暴力或其他方法。例如，将数组按非升序排序，然后从最大值开始，将每个值放入总和较小的数组中，在当前情况下给出正确答案：

public static int[][] alternative(int[] input) {
    int n = input.length;
    int[][] res = new int[2][n];

    int[] input0 = Arrays.copyOf(input, n);

    Arrays.sort(input0);

    System.out.println("Input: "+Arrays.toString(input)+", ordered: "+Arrays.toString(input0));

    int sum1 = 0, sum2 = 0;
    int a = 0, b = 0;

    for (int i = n-1; i >= 0; i--) {
        if (sum1 <= sum2) {
            res[0][a++] = input0[i];
            sum1 = sum1 + input0[i];
            System.out.println("Adding "+input0[i]+" into set 1 ==> Sum1 = "+sum1);
        } else {
            res[1][b++] = input0[i];
            sum2 = sum2 + input0[i];
            System.out.println("Adding "+input0[i]+" into set 2 ==> Sum2 = "+sum2);
        }
    }
    return res;
}

输出：

First example:
Input: [5, 8, 1, 1, 2, 3, 2], ordered: [1, 1, 2, 2, 3, 5, 8]
Adding 8 into set 1 ==> Sum1 = 8
Adding 5 into set 2 ==> Sum2 = 5
Adding 3 into set 2 ==> Sum2 = 8
Adding 2 into set 1 ==> Sum1 = 10
Adding 2 into set 2 ==> Sum2 = 10
Adding 1 into set 1 ==> Sum1 = 11
Adding 1 into set 2 ==> Sum2 = 11
[8, 2, 1, 0, 0, 0, 0], sum = 11
[5, 3, 2, 1, 0, 0, 0], sum = 11

Second example:
Input: [4, 6, 1, 2, 3, 3, 4], ordered: [1, 2, 3, 3, 4, 4, 6]
Adding 6 into set 1 ==> Sum1 = 6
Adding 4 into set 2 ==> Sum2 = 4
Adding 4 into set 2 ==> Sum2 = 8
Adding 3 into set 1 ==> Sum1 = 9
Adding 3 into set 2 ==> Sum2 = 11
Adding 2 into set 1 ==> Sum1 = 11
Adding 1 into set 1 ==> Sum1 = 12
[6, 3, 2, 1, 0, 0, 0], sum = 12
[4, 4, 3, 0, 0, 0, 0], sum = 11

对于输出中的 0，您可以编写一个简单的函数来创建一个没有 0 的新数组。

Answer 3

我们应该尝试所有组合。例如，如果数组是 (1,1,100,100)，则答案是 (100,1) (100,1)。如果数组是 (1,1,50,100)，则答案是 (1,1,50) (100)。我不认为这有任何捷径。如果数组有 N 个元素，那么我们将尝试所有组合 (Nc1, NcN01), (Nc2, NcN-2) .. 等等。然后找出他们之间的差异最小

如何将整数范围分成两个相等的部分

How to separate range of integers into two equal parts

java

arrays

integer

numbers