Anonymous user
Subset sum problem: Difference between revisions
→{{header|C}}: for listing all combos
(Updated D entry) |
(→{{header|C}}: for listing all combos) |
||
Line 242:
11 | 54 efferent
12 | -326 elysee
Code for listing ''all'' zero sum sets. It's pretty fast for this example, takes seconds even if printing all 300k+ combinations is enabled.
<lang c>#include <stdio.h>
#include <stdlib.h>
typedef struct { char* data; int weight; } item;
typedef struct { int sum; unsigned int mask; } sum_t;
item em[] = {
{"alliance", -624}, {"archbishop", -915}, {"balm", 397},
{"bonnet", 452}, {"brute", 870}, {"centipede", -658},
{"cobol", 362}, {"covariate", 590}, {"departure", 952},
{"deploy", 44}, {"diophantine", 645}, {"efferent", 54},
{"elysee", -326}, {"eradicate", 376}, {"escritoire", 856},
{"exorcism", -983}, {"fiat", 170}, {"filmy", -874},
{"flatworm", 503}, {"gestapo", 915}, {"infra", -847},
{"isis", -982}, {"lindholm", 999}, {"markham", 475},
{"mincemeat", -880}, {"moresby", 756}, {"mycenae", 183},
{"plugging", -266}, {"smokescreen", 423}, {"speakeasy", -745},
{"vein", 813}
};
#define N (sizeof(em)/sizeof(em[0]))
int cmp_sums(const void *a, const void *b)
{
return ((sum_t*)a)->sum - ((sum_t*)b)->sum;
}
sum_t *mksums(item *p, int n, int shift)
{
sum_t *r = malloc(sizeof(*r) * (1 << n));
int i;
for (i = 0; i < n; i++)
r[1<<i].sum = p[i].weight;
r[0].mask = 0, r[0].sum = 0;
for (i = 1; i < 1<<n; i++) {
unsigned int b = i & -(int)i;
r[i].mask = i << shift;
r[i].sum = r[i & ~b].sum + r[b].sum;
}
qsort(r, 1<<n, sizeof(*r), cmp_sums);
return r;
}
int main(void)
{
int n1 = N / 2, n2 = N - n1, i, j, i1, j1, sols = 0;
#define SHOW_ALL 1
#define N1 (1 << n1)
#define N2 (1 << n2)
sum_t *l = mksums(em, n1, 0),
*r = mksums(em + n1, n2, n1);
void showmask(unsigned int mask)
{
unsigned int m;
for (m = 0; (1<<m) <= mask; m++) {
if (mask & (1<<m))
printf("(%s,%d) ", em[m].data, em[m].weight);
}
if (mask) puts("");
}
int printlist() {
int x, y, s = (i1 - i) * (j - j1);
if (!l[i].sum) s--;
if (SHOW_ALL)
for (x = i; x < i1; x++)
for (y = j; y > j1; y--)
showmask(l[x].mask | r[y].mask);
return s;
}
i = 0, j = N2 - 1;
while (1) {
while (l[i].sum + r[j].sum) {
while (i < N1 && l[i].sum + r[j].sum < 0) i++;
while (j >= 0 && l[i].sum + r[j].sum > 0) j--;
if (i >= N1 || j < 0) break;
}
if (i >= N1 || j < 0) break;
for (i1 = i + 1; i1 < N1 && l[i1].sum == l[i].sum; i1++);
for (j1 = j - 1; j1 >= 0 && r[j1].sum == r[j].sum; j1--);
sols += printlist();
i = i1, j = j1;
}
printf("zero sums: %d\n", sols);
return 0;
}</lang>
=={{header|D}}==
| |||