最小设定差异

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). 
    } 

}