以相同的大小划分数组，使给定函数的值最小

Question

我遇到了以下问题陈述。

你有大小N的自然数的列表，你必须在两个列表A和大小N/2的B分配值，这样A元素的平方之和的B的乘最近的可能元素。

实施例： 考虑列表7 11 1 9 10 3 5 13 9 12
优化分布是：
名单A：5 9 9 12 13
列表B：1 3 7 10 11 （（5 + 9 + 9 + 12 + 13）^ 2 - （1 * 3 * 7 * 10 * 11））= 6
因此，您的程序应该输出6，这是最小值可以实现的差异。

我已经试过：

我已经试过贪婪的方法，以解决这个问题。我采取了两个变量sum和mul。现在我开始逐个从给定集合中获取元素，并尝试将其添加到两个变量中，并计算当前总和和乘法的当前平方。现在完成两个集合中的一个集合中的元素，以便组合给出最小可能值。

但是这种方法在给定的示例itselt中不起作用。我无法弄清楚这里可以使用什么方法。

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

编辑：

来源：CodinGame, Community puzzle

Answer 1

我不知道是否有在多项式时间内任何确切的解决方案。但是你可以尝试一种基于模拟退火的方法。

我的做法是：

1. 初始化listA的和数组listB到无序状态
2. 的概率为p运行贪婪的一步，否则运行随机步
3. 跟踪状态和相应的误差（使用HashMap）

贪婪步骤：找到一个元素，您可以在优化错误的列表之间移动。

随机步骤：从这两组中选择一个随机元素并计算错误。如果错误更好，请保留它。否则以q的概率保留它。

在这两个步骤中的任何一个，确保新的状态尚未探索（或至少阻止它）。

将p设置为较小的值（< 0.1），q可能取决于错误差异。

Answer 2

试试这个：从this stackoverflow answer采取

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维基百科的文章。