最小设定差异

我在这个名为codility的网站上遇到了这个问题,但我真的无法弄清楚如何解决它,会很感激帮助

给定n个整数的数组A,以及n个元素1或-1的序列S,我们定义值:

在此处输入图像描述

假设零元素的总和等于零。 写一个函数

int min_abs_sum(int[] A); 

比给定数组A的n个整数,范围[-100..100]计算val(A,S)的最低可能值(对于任何具有元素1或-1的序列S)。 您可以假设n <= 20000

例如给定数组:a = {1,5,2,-2}

你的函数应该返回0,因为对于序列S =( – 1,1,-1,1),val(A,S)= 0。

以下是一些人的结果的两个链接,它没有显示解决方案,但它确实显示了他们的算法的复杂性,第一个链接显示了程序应该运行的复杂性,第二个链接显示较慢。

第一个链接100%标记

第二个链接86%标记

这是分区问题的措辞不佳的版本。 您将把arraysA分成两组,尽可能接近相等。 具有较大总和的那个将在S数组中分配+1,而另一个组将获得-1。 选择分区问题的解决方案并调整它以返回此问题的答案。 实际上,它是分区的变体,寻求最佳可能值而不是2个相等的集合。

编辑这里是一些基于由@Jerry Coffin链接的论文的python代码

 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 = vx 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])) 

百万分之一的值是20000的一半(A中的最大数字)乘以100/2。 我使用了一个列表而不是一个数组,这意味着有些东西会比它们在文章中做得更快,速度更慢。 可以想象,通过将数字的前半部分相加并减去后半部分来实现最小值 - 或者类似于需要大的中间和的部分。 我使用的是列表而不是数组,但大小仍然有限。 对不起,我不做Java。

这基本上可以将两个部分的绝对值之和尽可能接近地分成两部分。

然后,您希望将这些元素乘以1或-1,以使一个分区全部为负,另一个分区全部为正。 当你这样做时,你总结它们以获得最终答案。

从算法的角度来看,我认为分区步骤几乎肯定是NP完全的(像“子集和”和“分区问题”这样的短语)。 从编程的角度来看,它非常简单 – 详尽地测试可能性,直到你得到最好的一个。 只要元素的数量很少(最多十几个[编辑:因为它是O(2 N ,你可以将它增加到30-40范围内的某个地方),它会相当快。

我相信它应该与O(N!)成比例,所以如果arrays变得很大,所以花费的时间很快就会变得不合理。 因为你只分成两组并且套内的顺序无关紧要,所以它是O(2 N )而不是O(N!)。 这种增长速度几乎没有O(N!)那么快,但仍然足够快,使大型集合无法处理。

然而,我应该补充一点,Codility似乎专注于最初看似NP完整的问题,但实际上并非如此 – 如果您错过了描述中的任何细节,问题可能会大大简化。

编辑:重读它,问题可能是忽略了一个关键细节:限制范围。 我不确定你是如何随意使用它的,但我非常确定它是否能够产生有效的解决方案。 我的直接猜测是,它基于类似于将基于比较的排序更改为计数(又称桶)排序。 我没有仔细考虑过任何真实细节……

编辑2:做一些观察(并由@Moron提示),有限的范围是重要的,我对它如何计算解决方案的思考通常是正确的。 @Moron非常友好地指出维基百科的子集和问题条目,但我没有发现特别好写的。 有点看起来出现了康奈尔的一篇论文,并附有解释,我发现它更清洁/更容易理解。

以下Java解决方案将在Codility中获得100%的分数。 我的解决方案基于由@Jerry Coffin链接的论文中的“重复元素分区”部分,但我还合并了几个额外的优化。

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

所以,目标是尽可能接近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取i的二进制来计算)并找到那样的min。

通过一些修改,您还可以获得S的正确值(如果这是一个要求。如果不是,那么将其作为一项要求可能会在面试中给你一些分数?)

这可能会很快:

 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中。 这用时间复杂度替换n和max_value。

仍然不确定正确性:(

 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*(hr) - 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(ni-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)