以相同的大小劃分數組，使給定函數的值最小

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