java - 最小设定差

Question

我在这个名为 codility 的网站上遇到了这个问题，但我真的不知道如何解决它，不胜感激

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

假设零元素之和为零。写一个函数

int min_abs_sum(int[] A);

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

例如给定数组:a={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 分成尽可能接近相等的 2 组。总和较大的一组将在 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。