java - 将数组分成相等大小，使得给定函数的值最小

Question

我遇到了以下问题陈述。

You have a list of natural numbers of size N and you must distribute the values in two lists A and B of size N/2, so that the squared sum of A elements is the nearest possible to the multiplication of the B elements.

Example: Consider the list 7 11 1 9 10 3 5 13 9 12.
The optimized distribution is:
List A: 5 9 9 12 13
List B: 1 3 7 10 11
which leads to the difference abs( (5+9+9+12+13)^2 - (1*3*7*10*11) ) = 6
Your program should therefore output 6, which is the minimum difference that can be achieved.

我尝试过的:

为了解决这个问题，我尝试了贪心法。我使用了两个变量 sum 和 mul。现在我开始从给定的集合中一个一个地获取元素并尝试将它添加到变量和计算电流中求和和乘法的平方。现在确定两个集合之一中的元素，以便组合给出最小可能值。

但是这种方法在给定的示例本身中不起作用。我不知道这里可以使用什么方法。

我不是要求解决方案的确切代码。任何可能的方法及其有效的原因都可以。

编辑:

来源:CodinGame, Community puzzle

Answer 1

试试这个:

import java.util.Arrays;

public class Test {

    public static void main(String [] args){
        int [] arr = {7, 11, 1, 9, 10, 3, 5, 13, 9, 12}; 
        int [][] res = combinations(5, arr);
        int N = Arrays.stream(arr).reduce(1, (a, b) -> a * b);
        int min = Integer.MAX_VALUE; 
        int [] opt = new int [5];
        for (int [] i : res){
            int k = (int) Math.abs( Math.pow(Arrays.stream(i).sum(), 2) - N/(Arrays.stream(i).reduce(1, (a, b) -> a * b)));
            if(k < min){
                min = k;
                opt = i;
            }
        }
        Arrays.sort(opt);
        System.out.println("minimum difference is "+ min + " with the subset containing this elements " + Arrays.toString(opt));
    }

    // returns all k-sized subsets of a n-sized set 
    public static int[][] combinations(int k, int[] set) {
        int c = (int) binomial(set.length, k);
        int[][] res = new int[c][Math.max(0, k)];
        int[] ind = k < 0 ? null : new int[k];
        for (int i = 0; i < k; ++i) { 
            ind[i] = i; 
        }
        for (int i = 0; i < c; ++i) {
            for (int j = 0; j < k; ++j) {
                res[i][j] = set[ind[j]];
            }
            int x = ind.length - 1;
            boolean loop;
            do {
                loop = false;
                ind[x] = ind[x] + 1;
                if (ind[x] > set.length - (k - x)) {
                    --x;
                    loop = x >= 0;
                } else {
                    for (int x1 = x + 1; x1 < ind.length; ++x1) {
                        ind[x1] = ind[x1 - 1] + 1;
                    }
                }
            } while (loop);
        }
        return res;
    }
    // returns n choose k; 
    // there are n choose k combinations without repetition and without observance of the sequence
    // 
    private static long binomial(int n, int k) {
        if (k < 0 || k > n) return 0;
        if (k > n - k) {
            k = n - k;
        }
        long c = 1;
        for (int i = 1; i < k+1; ++i) {
            c = c * (n - (k - i));
            c = c / i;
        }
        return c;
    }
}

代码取自 this stackoverflow answer , 也看看 this关于组合的维基百科文章。