将列表分成两部分,它们的总和彼此最接近

Question

这是一个硬算法问题:

将列表分成两部分(总和),它们的总和最接近(大多数)彼此

列表长度为1 <= n <= 100且问题中给出的(数字)权重1 <= w <= 250.

例如:23 65 134 32 95 123 34

1.sum = 256

2.sum = 250

1.list = 1 2 3 7

2.list = 4 5 6

我有一个算法,但它并不适用于所有输入.

1. 在里面.列表list1 = [],list2 = []
2. 排序元素(给定列表)[23 32 34 65 95 123 134]
3. 弹出最后一个(最多一个)
4. 插入到不同的列表中

实现:list1 = [],list2 = []

1. 选择134插入列表1.list1 = [134]
2. 选择123插入列表2.因为如果你插入list1差异越来越大
   3.选择95并插入list2.因为sum(list2)+ 95 - sum(list1)较少.

等等...

Answer 1

你可以将其重新表述为背包问题.

您有一个总重量为M的物品清单,应安装在可容纳最大重量M/2的垃圾箱中.包装在垃圾箱中的物品应尽可能重,但不要超过垃圾箱.

对于所有权重都是非负的情况,这个问题只是NP完全弱的并且具有多项式时间解.

可以在Wikipedia上找到针对此问题的动态编程解决方案的描述.

Answer 2

问题是NPC，但是有一个伪多项式算法可以解决它，这是一个2-分区问题，您可以按照子集和问题的伪多项式时间算法的方式来解决这个问题。如果输入大小与输入值多项式相关，那么这可以在多项式时间内完成。

在你的情况下（权重<250）它是多项式（因为权重<=250n=>总和<=250n^2）。

令Sum = 权重之和，我们要创建二维数组A，然后逐列构造A

如果（j == 权重[i] 或 j - 权重[i] = 权重[k]（k 在列表中）），A[i,j] = true。

使用此算法创建数组需要 O(n^2 * sum/2)。

最后我们应该找到最有价值的、具有真正价值的专栏。

这是一个例子：

项目：{0,1,2,3} 权重：{4,7,2,8} => 总和 = 21 总和/2 = 10

items/weights 0|  1  | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10    
  --------------------------------------------------------- 
  |0             |  0  | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0
  |1             |  0  | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0
  |2             |  0  | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1
  |3             |  0  | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1

因为 a[10, 2] == true 分区是 10, 11

这是我在这里找到的算法并进行了一些编辑以解决您的问题：

bool partition( vector< int > C ) {
 // compute the total sum
 int n = C.size();
 int N = 0;
 for( int i = 0; i < n; i++ ) N += C[i];
 // initialize the table 
 T[0] = true;
 for( int i = 1; i <= N; i++ ) T[i] = false;
 // process the numbers one by one
 for( int i = 0; i < n; i++ )
  for( int j = N - C[i]; j >= 0; j--)
   if( T[j] ) T[j + C[i]] = true;

 for(int i = N/2;i>=0;i--)
    if (T[i])
      return i;
 return 0;
}

我只是返回第一个 T[i]，这是 true，而不是返回 T[N/2] （按从最大到最小的顺序）。

找到给出这个值的路径并不难。