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

问题是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]（以最大到最小的顺序），这是正确的。

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