Недавно я решил эту проблему, используя динамическое программирование на c ++.Я не изменил код, чтобы ответить на ваш вопрос.Но изменение некоторых констант и небольшого кода должно сработать.
Приведенный ниже код считывает и решает N проблем. Каждая проблема имеет несколько человек (в вашем случае число целых чисел) и их вес (целочисленные значения).Этот код пытается разбить набор на 2 группы с минимальной разницей.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_PEOPLE 100
#define MAX_WEIGHT 450
#define MAX_WEIGHT_SUM MAX_PEOPLE*MAX_WEIGHT
using namespace std;
int weights[MAX_PEOPLE];
//bool table[MAX_PEOPLE + 1][MAX_WEIGHT_SUM + 1];
bool** create2D(int x, int y) {
bool **array = new bool*[x];
for (int i = 0; i < x; ++i) {
array[i] = new bool[y];
memset(array[i], 0, sizeof(bool)*y);
}
return array;
}
void delete2D(int x, int y, bool **array) {
for (int i = 0; i < x; ++i) {
delete[] array[i];
}
delete[] array;
}
void memset2D(int x, int y, bool **array) {
for(int i = 0; i < x; ++i)
memset(array[i], 0, sizeof(bool)*y);
}
int main(void) {
int n, N, W, maxDiff, teamWeight, temp;
int minWeight = MAX_WEIGHT, maxWeight = -1;
cin >> N;
while(N--) {
cin >> n;
W = 0;
for(int i = 0; i < n; ++i) {
cin >> weights[i];
if(weights[i] < minWeight)
minWeight = weights[i];
if(weights[i] > maxWeight)
maxWeight = weights[i];
W += weights[i];
}
int maxW = maxWeight + (W>>1);
int maxn = n>>1;
int index = 0;
/*
table[j][i] = 1 if a team of j people can form i weight
from K people, where k is implicit in loop
table[j][i] = table[j-1][i-weight[j]] if i-weight[j] >=0
*/
bool **table = create2D(maxn+1, maxW+1);
//memset2D(maxn+1, maxW+1, table);
//memset(table, 0, sizeof(table));
table[0][0] = true;
/* for k people what can be formed?*/
for(int k = 0; k < n; ++k) {
/* forming team of size j out of k people*/
for(int j = min(k, maxn) ; j >= 1; --j) {
/* using j people out of k, can I make weight i?*/
for(int i = maxW; i >=minWeight ; --i) {
if (table[j][i] == false) {
/*do not consider k if more than allowable*/
index = i - weights[k];
if (index < 0) break;
/*if without adding k, we can make the weight
limit with less than one person then one can
also make weight limit by adding k.*/
table[j][i] = table[j-1][index];
} /*outer if ends here*/
} /* ith loop */
} /* jth loop */
} /* kth loop */
maxDiff = MAX_WEIGHT_SUM ;
teamWeight = 0;
for(int i = 0; i <= maxW; ++i) {
if (table[n/2][i]) {
temp = abs(abs(W - i) - i);
if (temp < maxDiff) {
maxDiff = temp;
teamWeight = i;
}
}
}
delete2D(n+1, maxW+1, table);
teamWeight = min(teamWeight, W-teamWeight);
cout << teamWeight << " " << W - teamWeight << endl;
if(N)
cout << endl;
}
return 0;
}