从平衡子集和有效地跟踪集的和？

Question

平衡子集和问题被描述为将阵列分成两个子集，使得两个子集和的差最小，最好的情况是两个子集和相等。

注意：-我们不能离开原始集合中的元素。

现在，我需要得到最小差分划分的集合1和集合2的和，我已经使用O（sum*sum*n）解决方案找到了集合的和，但为了我所做的工作，我需要一些复杂度更好的东西。如何在比O（sum*sum*n）更短的时间内解决这个问题？

我的 O（N^3） 方法如下： 注意：-s1，s2，s3 是静态变量，总和是数组的总和。

static int partition(int sum1, int sum2, ArrayList < Integer > arr, int i) {
 if (i == arr.size()) {
  if (Math.abs(sum1 - sum2) < s3) {
   s1 = sum1;
   s2 = sum2;
   s3 = Math.abs(sum1 - sum2);
  }

  return Math.abs(sum1 - sum2);

 }
 if (dp[(sum1 < 0) ? 2 * sum - sum1 : sum1][(sum1 < 0) ? 2 * sum - sum1 : sum1][i] != 0)
  return dp[(sum1 < 0) ? 2 * sum - sum1 : sum1][(sum1 < 0) ? 2 * sum - sum1 : sum1][i] > 0 ? dp[(sum1 < 0) ? 2 * sum - sum1 : sum1][(sum1 < 0) ? 2 * sum - sum1 : sum1][i] - 1 : dp[(sum1 < 0) ? 2 * sum - sum1 : sum1][(sum1 < 0) ? 2 * sum - sum1 : sum1][i];


 int c1 = partition(sum1 +  arr.get(i), sum2, arr, i + 1);
 int c2 = partition(sum1, sum2 +  arr.get(i), arr, i + 1);

 if (Math.abs(c1) < Math.abs(c2)) {
  dp[(sum1 < 0) ? 2 * sum - sum1 : sum1][(sum1 < 0) ? 2 * sum - sum1 : sum1][i] = c1 >= 0 ? c1 + 1 : c1;
  return c1;
 } else {
  dp[(sum1 < 0) ? 2* sum - sum1 : sum1][(sum1 < 0) ? 2 * sum - sum1 : sum1][i] = c2 >= 0 ? c2 + 1 : c2;
  return c2;
 }

}

Answer 1

我认为您应该使用在O（sum*n）中运行的伪多项式算法，尽管注释中建议使用O（2^n）蛮力方法也应该有效。

这个想法类似于背包的伪多项式算法：找到所有组合值小于或等于MAX=sum/2的可能分区。这些分区中最大的将是您正在寻找的分区。

下面是一个可能的python实现:

def min_partition_diff(items):
    summed=sum(items)
    MAX=summed//2


    value_reachable=[False]*(MAX+1)    
    value_reachable[0]=True #at the beginning only the empty set with value 0 is reachable

    #update all possible configurations:
    for item in items:
        for i in reversed(range(MAX)):# //backwards->object at most once in every configuration!
            if value_reachable[i]:#update configuration only if it can be constructed with earlier items
               next_reachable_value = i+item
               if next_reachable_value <= MAX:
                    value_reachable[next_reachable_value]=True

    biggest_value_possible=MAX - value_reachable[::-1].index(True)# find last True in the values

    return summed-2*biggest_value_possible # this is the smallest difference