解題思路：
枚舉所有物品的子集，然后再枚舉子集的組合，數(shù)據(jù)量很小，不需要剪枝。
#include <iostream>
#include <cmath>
using namespace std;
struct Stack 
{
int a[100];
int top;
int num;
}stack, buf[100], rou;
int top;
int num[1001];
double am;
int c, s;
int hash[100];
double Min;
int u;
void dfs(int index) {
int i;
buf[top].top = stack.top;
for(i = 0; i < stack.top;i++){
buf[top].a[i] = stack.a[i];
}
top ++;
for(i = index; i < s; i++) {
if(hash[i] == 1)
continue;
if(stack.top == 2)
continue;
stack.a[ stack.top++ ] = i;
hash[i] = 1;
dfs(i+1);
hash[i] = 0;
stack.top --;
}
}
void DFS(int index, int sum) {
int i, j;
if(stack.top > c)
return ;
if(sum == (1<<s) - 1) {
double sz = 0, sl;
for(i = 0; i < stack.top; i++) {
sl = 0;
for(j = 0; j < buf[ stack.a[i] ].top; j++) {
int y = buf[ stack.a[i] ].a[j];
sl += num[y];
}
sz += fabs(am - sl);
}
for(i = stack.top; i < c; i++) {
sz += fabs(am);
}
if(sz < Min) {
Min = sz;
rou.top = 0;
for(i = 0; i < stack.top; i++) {
rou.a [rou.top ++] = stack.a[i];
}
for(i = stack.top; i < c; i++) {
rou.a[ rou.top++ ] = 0;
}
rou.top = c;
}
return ;
}
for(i = index; i < top; i++) {
if(hash[i])
continue;
if(sum & buf[i].num)
continue;
stack.a[ stack.top ++ ] = i;
hash[i] = 1;
DFS(i+1, (sum|buf[i].num) );
hash[i] = 0;
stack.top --;
}
}
int main() {
int i, j;
int cas = 1;
while(scanf("%d %d", &c, &s) != EOF) {
am = 0;
Min = 1000000000.0;
for(i = 0; i < s; i++) {
scanf("%d", &num[i]);
am += num[i];
hash[i] = 0;
}
am /= c;
stack.top = 0;
top = 0;
dfs(0);
for(i = 0; i < top; i++) {
buf[i].num = 0;
for(j = 0; j < buf[i].top; j++) {
buf[i].num |= (1<<(buf[i].a[j]));
}
}
memset(hash, 0, sizeof(hash));
stack.top = 0;
DFS(0, 0);
printf("Set #%d\n", cas ++);
int rt = 0;
for(i = 0; i < rou.top; i++) {
if(rou.a[i]) {
printf(" %d:", rt ++);
for(j = 0; j < buf[ rou.a[i] ].top; j++)
printf(" %d", num[ buf[ rou.a[i] ].a[j] ]);
puts("");
}
}
for(i = rt; i < c; i++)
printf(" %d:\n", i);
printf("IMBALANCE %.5lf\n", Min);
puts("");
}
return 0;
}