最小設定差異

Question

我碰到這個網站名爲codility關於這個問題，但我不能真正弄清楚如何解決它，希望得到幫助

給定n個整數數組A和n的序列S元件1或-1我們定義的值：

假設零種元素的總和等於零。 寫功能

int min_abs_sum(int[] A); 

比元件1或給定的n個整數的從[-100..100]計算VAL（A，S）的最低可能值的範圍內的陣列A（用於任何序列S -1）。你可以假設n < = 20000。

例如給定的數組： 一個= {1,5,2，-2}

您的函數應返回0，因爲對於序列S =（ - 1,1，-1,1）的VAL （A，S）= 0。

這裏有兩個鏈接對於一些人的結果，它沒有顯示解決方案，但它確實顯示了他們的算法的複雜性，第一個鏈接顯示程序運行的複雜性，第二個鏈接更慢。

1st link 100% marks

2nd link 86% marks

Answer 1

這是分區問題的措辭不當。您將盡可能接近相等地將陣列A分成兩組。一個總數較大的人將在S數組中分配+1，另一個組將得到-1。選擇分區問題的解決方案並調整它以返回此問題的答案。實際上，它是分區的變體，尋求最佳可能值，而不是2個相等的集合。

編輯這裏是基於由@Jerry棺材

def min_abs_sum(A): 
vals = [] 
for x in A: 
    for v in vals: 
     n = v+x 
     if (abs(n)<=1000000) and (n not in vals): vals.append(n) 
     n = v-x 
     if (abs(n)<=1000000) and (n not in vals): vals.append(n) 
    if (x not in vals): vals.append(x) 
    if (-x not in vals): vals.append(-x) 
return (min([abs(x) for x in vals])) 

一個百萬價值鏈接的紙一些Python代碼爲20000（以A MAX數）乘以100/2的一半。我使用了一個列表而不是一個數組，這意味着有些事情會比文章中的速度更快，速度更慢。可以想象，最小值是通過將前半部分數字相加並減去後半部分來實現的，或者類似於需要大量中間和的東西。我使用的是列表而非數組，但大小仍然有限。對不起，我沒有做Java。

Answer 2

所以，我們的目標是獲得儘可能接近0越好。

我首先想到的是，我會按降序排序的數組，然後在列表上迭代做這樣的事情：

int total = 0; 
foreach(int i in a) 
{ 
    total = Math.Min(Math.Abs(total - i), Math.Abs(total + i)); 
} 

這將工作a={1,5,2,-2}（總量將是以下5,4,2,0）

但我不確定它是否適用於所有情況。我會仔細研究一下，看看是否有不適合的情況。

編輯：

好吧，我猜蠻力將工作？

public static int MinArray(int[] array) 
    { 
     int val = int.MaxValue; 

     for (int i = 0; i < Math.Pow(2, array.Length); i++) 
     { 
      val = Math.Min(CalcMin(array, i), val); 
     } 

     return val; 
    } 

    private static int CalcMin(int[] array, int negs) 
    { 
     int ret = 0; 

     for (int i = 0; i < array.Length; i++) 
     { 
      int neg = 1; 

      if (negs != 0) 
      { 
       neg = negs % 2 == 1 ? -1 : 1; 
       negs >>= 1; 
      } 
      ret += array[i] * neg; 
     } 

     return Math.Abs(ret); 
    } 

所以，我在做什麼走S的每個迭代（這是由我走在MinArray二進制計算），並找到最小的方式。

通過修改基因的一點點，你也可以得到對S中的正確的值（如果這是必需的。如果不是，使其成爲一個要求可能得分，你在採訪中一些點？）

Answer 3

這基本上可以將a劃分爲兩部分，其中兩部分的絕對值之和儘可能接近相等。

然後，您想將這些元素乘以1或-1，以使一個分區全部爲負，另一個分區全部爲正。當你這樣做，你總結他們得到最終答案。

從算法的角度來看，我認爲分割步驟幾乎可以肯定是NP-完全（像「子集總和」和「分區問題」這樣的詞組）出現在腦海中。從編程的角度來看，它非常簡單 - 儘可能詳盡地測試可能性，直到獲得最佳效果。只要元素的數量很少（最多可達十幾個[編輯：因爲它是O（2 ^N，你可能會增加到30-40範圍內的某個地方），它會相當快。

雖然我認爲它應該與O（N！）成正比，所以如果數組變大，所花費的時間將會很快變得不合理 由於您只分成兩組，並且在組內不排序這不是O（N！），它的增長速度幾乎不如O（N！）快，但仍然足以使大型設備無法處理。

但是，我應該補充說，Codility似乎是sp在可能最初似乎是NP完全但是實際上不是 - 如果您在描述中遺漏了任何細節的問題中，可能會特別容易解決問題。

編輯：重讀它，問題可能是我忽略了一個關鍵的細節：受限制的範圍。我不確定你如何使用它，但我相當確信這是生產高效解決方案的關鍵。我的猜測是它基於類似於將基於比較的排序改爲計數（又名桶）排序的東西。我沒有想過通過它在任何真正的細節，雖然...

編輯2：做一點看（和由@Moron提示），有限的範圍是重要的，我的想法是如何形成一個解決方案基本正確。 @Moron非常友好地指出維基百科條目的子集總和問題，但我沒有發現寫得特別好。有點看起來出現了一個paper from Cornell與解釋我發現一點清潔/更容易理解。

Answer 4

這可能可能工作速度快：

maxvalue = 100 

def solve(data): 
    def mark_sum(s): 
     # wrap sum around maxvalue 
     if s >= maxvalue: 
      s -= maxvalue * 2 
     elif sum < -maxvalue: 
      s += maxvalue * 2 
     # mark sum 
     if s >= 0: 
      s_new_pos[s] = True 
     else: 
      s_new_neg[s + maxvalue] = True 

    s_old_pos = [False] * maxvalue # marks for sums [0..99] 
    s_old_neg = [False] * maxvalue # marks for sums [-100..-1] 
    s_old_pos[0] = True # seed array with zero sum for zero elements 
    for n in data: 
     s_new_pos = [False] * maxvalue 
     s_new_neg = [False] * maxvalue 
     for i in range(maxvalue): # mark new possible sums 
      if s_old_pos[i]: 
       mark_sum(i + n) 
       mark_sum(i - n) 
      if s_old_neg[i]: 
       mark_sum(i - 100 + n) 
       mark_sum(i - 100 - n) 
     s_old_pos = s_new_pos 
     s_old_neg = s_new_neg 
    for i in range(maxvalue): 
     if s_old_pos[i]: 
      return i 
     if s_old_neg[-1 - i]: 
      return abs(-1 - i) 
    raise AssertionError('my bad') 

無需檢查所有可能的總和（高達1000000）。他們可以只是圍繞max_value。這在時間複雜度上用max_value代替n。

仍然不確定正確性:(

Answer 5

def min_abs_sum(A): 
    A[:] = sorted([ abs(i) for i in A if i != 0 ], reverse=True) 
    s = sum(A) 
    h = s/2 
    r = find_balance_iter(h, A) 
    return abs(2*(h-r) - s) 

def find_balance_iter(v, A): 
    r = v 
    n = len(A) 
    for i in xrange(n): 
     if i and A[i] == A[i-1]: 
      continue 
     for j in xrange(n-i-1): 
      vv = v - A[i] 
      rr = vv 
      AA = A[i+j+1:] 
      while True: 
       if vv == 0 or vv in AA: 
        return 0 
       if vv < 0 or not AA: 
        rr = vv 
        break 
       if vv < AA[-1]: 
        rr = min(vv-AA[-1], rr, key=compare) 
        break 
       vv -= AA[0] 
       AA[:] = AA[1:] 
      r = min(r, rr, key=compare) 
    return r 

def compare(a): 
    return (abs(a), a) 

Answer 6

下面的Java解決方案將在Codility得分100％。我的解決方案是基於由@Jerry棺材掛紙的部分「有重複的元素分區」，但我還包含了一些額外的優化。

import java.util.Arrays; 

class Solution { 

    public int solution (int[] A) { 

     int n=A.length,r=0,c=1,sum=0,mid=0; 

     // Add all numbers, replace them with their absolute value, and sort them 
     for(int i=0;i<n;i++) { 
      A[i]=Math.abs(A[i]); 
      sum+=A[i]; 
     } 
     Arrays.sort(A); // This minimizes the speed of growth of r in the loop below and allows us to count duplicates while scanning the array 
     mid=sum/2; // If the number is odd the result is rounded down (the best possible solution is 1 instead of 0). 

     // Find the subset of numbers whose sum is closest to half the total sum  
     boolean[] bs=new boolean[mid+101]; // We only need to check sets that are equal or less than half the sum of the numbers (to avoid having to check the sum in the inner loop I sacrifice 100 booleans since 100 is the maximum value allowed) 
     bs[0]=true; // The set with zero elements always adds to 0 
     for(int i=0;i<n;i++){ 
      if(A[i]==0) continue; 
      // Count duplicate entries 
      if(i<n-1 && A[i]==A[i+1]){ 
      c++; 
      continue; 
      } 
      // Scan the subset sum result array from right to left and add A[i] c times to existing subset sums 
      for (int j = r; j >= 0; j--) 
      if(bs[j]){ 
       int m= Math.min(mid, j+A[i]*c); 
       for(int k= j+A[i];k<=m && !bs[k];k+=A[i]) bs[k]=true; // To avoid duplicate work when dealing with multiples of previous numbers the loop stops if we find an entry has already been set. 
      } 
      r=Math.min(mid, r+A[i]*c); // New rightmost subset sum can be no more than the mid point 
      while(!bs[r]) r--; // Scan back to rightmost subset sum 
      if(r==mid) break; // Found an optimal solution; no need to continue 
      c=1; 
    } 
    return sum-2*r; // The rightmost subset sum that does not go over half the sum is the best solution, compute the difference of the complementary subsets (r and sum-r). 
    } 

}