问题是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]（以最大到最小的顺序），这是正确的。
寻找给出该值的路径并不难。
