Tôi đã giải quyết vấn đề này gần đây bằng cách sử dụng Lập trình động trong C++. Tôi chưa sửa đổi mã để trả lời câu hỏi của bạn. Nhưng thay đổi một số hằng số và ít mã nên làm.
Đoạn mã dưới đây đọc và giải quyết các sự cố N. Mỗi sự cố có một số người (trong số trường hợp của bạn là số nguyên) và trọng số của chúng (giá trị số nguyên). Mã này cố gắng chia bộ thành 2 nhóm với sự khác biệt là tối thiểu.
#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;
}
Nhấn mạnh: OP là không quan tâm đến việc xây dựng ** ** các tập con, chỉ trong việc có được mức tối thiểu.Cho dù nó có thể làm như vậy mà không xây dựng các tập con là một vấn đề mở của khóa học. –