分区整数列表，以减少他们的款项的差额 [英] Partitioning a list of integers to minimize difference of their sums

问题描述

由于整数列表→，我怎么能分割成2列出 A 和 B ，使得 D（A，B）= ABS（SUM（一） - 和（B））最小。我知道这个问题是NP完全的，所以我要寻找一个伪多项式时间算法即 0（C * N），其中 C =总和（L地图ABS）。我看着维基百科但算法有它分割成精确半部分是一个特殊的案例我所期待的......

编辑： 为了澄清，我正在寻找的分区 A 和 B 并不仅仅是产生的最小差值 D（A，B）

要一概而论，什么是伪多项式时间算法来划分的 N 编号为 K 组的列表 G1，G2 ... GK ，使得（MAX（S） - 分（S））。ABS 是为越小越好，其中 S = [总和（G1），和（G2），...总和（GK）]

解决方案

一个幼稚的，琐碎的，仍然伪多项式的解决办法是使用现有的解决方案，子集和，并重复 SUM（阵列）/ 2 0（并返回找到的第一个）。

该解决方案的复杂性将是 0（W ^ 2 * N），其中是W 是的总和数组。

伪code：

 的C和来自总和（阵列）/ 2比0降：
   子集LT;  -  subsetSumSolver（阵列，C和）
   如果子！= NULL：
        返回集
 

上面将返回的最大子集是低级/等于总和（阵列）/ 2 ，而另一部分是补为返回子集

---

然而，动态规划的子集之和应该足够了。

回想一下，计算公式为：

  F（0，I）=真
F（X，0）= FALSE |某某歌！= 0
函数f（x，i）的= F（X-改编[I]中，I-1）或F（X，I-1）的
 

在构建矩阵，上述实际创建你的每一行与值低于初始 X ，如果你输入的总和（阵列）/ 2 - 它基本上所有的值

在生成DP矩阵，只要找到了 X ，使得 F（X，N）=真，这是你能得到的最好的分区。

复杂性在这种情况下是 0（WN）

Given a list of integers l, how can I partition it into 2 lists a and b such that d(a,b) = abs(sum(a) - sum(b)) is minimum. I know the problem is NP-complete, so I am looking for a pseudo-polynomial time algorithm i.e. O(c*n) where c = sum(l map abs). I looked at Wikipedia but the algorithm there is to partition it into exact halves which is a special case of what I am looking for...

EDIT: To clarify, I am looking for the exact partitions a and b and not just the resulting minimum difference d(a, b)

To generalize, what is a pseudo-polynomial time algorithm to partition a list of n numbers into k groups g1, g2 ...gk such that (max(S) - min(S)).abs is as small as possible where S = [sum(g1), sum(g2), ... sum(gk)]

解决方案

A naive, trivial and still pseudo-polynomial solution would be to use the existing solution to subset-sum, and repeat for sum(array)/2to 0 (and return the first one found).

Complexity of this solution will be O(W^2*n) where W is the sum of the array.

pseudo code:

for cand from sum(array)/2 to 0 descending:
   subset <- subsetSumSolver(array,cand)
   if subset != null:
        return subset

The above will return the maximal subset that is lower/equals sum(array)/2, and the other part is the complement for the returned subset.

---

However, the dynamic programming for subset-sum should be enough.

Recall that the formula is:

f(0,i) = true
f(x,0) = false | x != 0
f(x,i) = f(x-arr[i],i-1) OR f(x,i-1)

When building the matrix, the above actually creates you each row with value lower than the initial x, if you input sum(array)/2 - it's basically all values.

After you generate the DP matrix, just find the maximal value of x such that f(x,n)=true, and this is the best partition you can get.

Complexity in this case is O(Wn)

这篇关于分区整数列表，以减少他们的款项的差额的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！