将列表分为两部分，它们的和彼此最接近

小编典典

将列表分为两部分，它们的和彼此最接近

algorithm

这是一个 很难解决的 算法问题：

将列表分为两部分（总和），它们的总和彼此最接近（最接近）

列表长度为1 <= n <= 100，并且其（数字）权重为1 <= w <= 250（在问题中给出）。

例如：23 65 134 32 95 123 34

1.sum = 256

2.sum = 250

1.清单= 1 2 3 7

2.清单= 4 5 6

我有一个算法，但不适用于所有输入。

在里面。列出list1 = []，list2 = []
排序元素（给定列表）[23 32 34 65 95 123 134]
弹出最后一个（最多一个）
插入差异较小的列表

实现：list1 = []，list2 = []

选择134插入列表1。list1 = [134]
选择123插入list2。因为如果您插入list1，差异
会变大3.选择95并插入list2。因为sum（list2）+ 95-sum（list1）较小。

等等…

阅读 246

2020-07-28

共1个答案

小编典典

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

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

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

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

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

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

这是一个例子：

项目：{0,1,2,3}权重：{4,7,2,8} => sum = 21 sum / 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]，而不是返回T [N / 2]（以最大到最小的顺序），这是正确的。

寻找给出该值的路径并不难。

2020-07-28