最小设定差异
我在这个名为codility的网站上遇到了这个问题,但是我真的无法弄清楚如何解决它,会很感激帮助
给定n个整数的数组A,以及n个元素1或-1的序列S,我们定义值:
假设零元素的总和等于零.写一个函数
int min_abs_sum(int[] A);
如果给定一个数组A,则来自[-100..100]范围的n个整数计算val(A,S)的最低可能值(对于任何具有元素1或-1的序列S).您可以假设n <= 20000.
例如给定的数组:a = {1,5,2,-2}
你的函数应该返回0,因为对于序列S =( - 1,1,-1,1),val(A,S)= 0.
以下是一些人的结果的两个链接,它没有显示解决方案,但它确实显示了他们的算法的复杂性,第一个链接显示程序应该运行的复杂性,第二个链接显示较慢.
这是分区问题的措辞不佳的版本.您将把阵列A分成两组,尽可能接近相等.具有较大总和的那个将在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 = 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]))
百万分之一的值是20000的一半(A中的最大数字)乘以100/2.我使用了一个列表而不是一个数组,这意味着有些东西会比它们在文章中做的更快,速度更慢.可以想象,通过将数字的前半部分相加并减去后半部分来实现最小值 - 或者类似于需要大量中间和的那些.我使用的是列表而不是数组,但大小仍然有限.对不起,我不做Java.
这基本上可以a分成两部分,两部分的绝对值之和尽可能接近相等.
然后,您希望将这些元素乘以1或-1,以使一个分区全部为负,另一个分区全部为正.当你这样做时,你总结它们以获得最终答案.
从算法的角度来看,我认为分区步骤几乎肯定是NP完全的(像"子集和"和"分区问题"这样的短语).从编程的角度来看,它非常简单 - 详尽地测试可能性,直到你得到最好的一个.只要元素的数量很少(最多十几个[编辑:因为它是O(2 N,你可以将它增加到30-40范围内的某个地方),它会相当快.
我认为它应该与O(N!)成比例,所以如果阵列变得很大,所以花费的时间很快就会变得不合理.由于你只分成两组并且套内的顺序无关紧要,所以它是O(2 N)而不是O(N!).这并没有像O(N!)那样快速增长,但仍然足够快,使大型集合无法处理.
然而,我应该补充一点,Codility似乎专注于最初看似NP完整的问题,但实际上并非如此 - 如果您错过了描述中的任何细节,问题可能会大大简化.
编辑:重读它,问题可能是我忽略了一个关键细节:限制范围.我不确定你是如何随意使用它的,但我很确定它是否能够产生有效的解决方案.我的直接猜测是,它基于类似于将基于比较的排序更改为计数(又称桶)排序.我没有仔细考虑过任何真实细节......
编辑2:做一些观察(并由@Moron提示),有限的范围是重要的,我对它如何计算解决方案的思考通常是正确的.@Moron非常友好地指出维基百科的子集和问题条目,但我没有发现特别好写的.看起来有点看起来康奈尔的一篇论文带有解释,我发现它有点清洁/更容易理解.
| 归档时间： |
|
| 查看次数： |
3480 次 |
| 最近记录： |