Subset sum problem: Difference between revisions
Content deleted Content added
J |
→{{header|C}}: shorten the example, to show all the zero sum subsets, you can kill the process if you got all you need from it. and its easier to follow without the bit math which doesn't change the time complexity anyway. |
||
Line 166: | Line 166: | ||
<lang c>#include <stdio.h> |
<lang c>#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <stdint.h> |
|||
#include <string.h> |
|||
typedef struct { |
typedef struct { |
||
char *word; |
|||
int weight; |
|||
} item_t; |
|||
item_t items[] = { |
|||
uint64_t subsum(item *x, int n) |
|||
{"alliance", -624}, |
|||
{ |
|||
{"archbishop", -915}, |
|||
int i, j, w, from, to, step, pos = 0, neg = 0; |
|||
{"balm", 397}, |
|||
uint64_t bit, *buf; |
|||
{"bonnet", 452}, |
|||
{"brute", 870}, |
|||
for (i = 0; i < n; i++) |
|||
{"centipede", -658}, |
|||
if (x[i].weight >= 0) pos += x[i].weight; |
|||
{"cobol", 362}, |
|||
else neg += x[i].weight; |
|||
{"covariate", 590}, |
|||
{"departure", 952}, |
|||
buf = calloc(pos - neg + 1, sizeof(uint64_t)); |
|||
{"deploy", 44}, |
|||
buf -= neg; |
|||
{"diophantine", 645}, |
|||
{"efferent", 54}, |
|||
for (i = 0; i < n; i++) { |
|||
{"elysee", -326}, |
|||
w = x[i].weight; |
|||
{"eradicate", 376}, |
|||
bit = (uint64_t)1 << i; |
|||
{"escritoire", 856}, |
|||
{"exorcism", -983}, |
|||
if (w < 0) from = neg, to = pos + 1, step = 1; |
|||
{"fiat", 170}, |
|||
{"filmy", -874}, |
|||
{"flatworm", 503}, |
|||
for (j = from; j != to; j += step) |
|||
{"gestapo", 915}, |
|||
if (buf[j]) buf[j + w] = buf[j] | bit; |
|||
{"infra", -847}, |
|||
buf[w] = bit; |
|||
{"isis", -982}, |
|||
{"lindholm", 999}, |
|||
if (buf[0]) break; |
|||
{"markham", 475}, |
|||
} |
|||
{"mincemeat", -880}, |
|||
{"moresby", 756}, |
|||
bit = buf[0]; |
|||
{"mycenae", 183}, |
|||
free(buf + neg); |
|||
{"plugging", -266}, |
|||
{"smokescreen", 423}, |
|||
return bit; |
|||
{"speakeasy", -745}, |
|||
} |
|||
{"vein", 813}, |
|||
int main(void) |
|||
{ |
|||
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} |
|||
}; |
|||
uint64_t i, v, ret = subsum(em, sizeof(em)/sizeof(em[0])); |
|||
if (!ret) { |
|||
puts("no zero sums\n"); |
|||
return 1; |
|||
} |
|||
puts("Found zero sum:"); |
|||
for (i = 0; i < 64; i++) { |
|||
v = (uint64_t)1 << i; |
|||
if (ret & v) |
|||
printf("%2llu | %5d %s\n", i, em[i].weight, (char*)em[i].data); |
|||
} |
|||
return 0; |
|||
}</lang>{{out}} |
|||
Found zero sum: |
|||
1 | -915 archbishop |
|||
2 | 397 balm |
|||
3 | 452 bonnet |
|||
5 | -658 centipede |
|||
8 | 952 departure |
|||
9 | 44 deploy |
|||
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 { const 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 n = sizeof (items) / sizeof (item_t); |
|||
int cmp_sums(const void *a, const void *b) |
|||
int *path; |
|||
{ |
|||
return ((const sum_t*)a)->sum - ((const sum_t*)b)->sum; |
|||
} |
|||
void subsum (int i, int weight) { |
|||
int j; |
|||
{ |
|||
if (i && !weight) { |
|||
sum_t *r = malloc(sizeof(*r) * (1 << n)); |
|||
for (j = 0; j < i; j++) { |
|||
int i; |
|||
item_t item = items[path[j]]; |
|||
for (i = 0; i < n; i++) |
|||
printf("%s%s", j ? " " : "", items[path[j]].word); |
|||
r[1<<i].sum = p[i].weight; |
|||
} |
|||
printf("\n"); |
|||
r[0].mask = 0, r[0].sum = 0; |
|||
} |
|||
for (j = i ? path[i - 1] + 1: 0; j < n; j++) { |
|||
path[i] = j; |
|||
subsum(i + 1, weight + items[j].weight); |
|||
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( |
int main () { |
||
path = malloc(n * sizeof (int)); |
|||
{ |
|||
subsum(0, 0); |
|||
int n1 = N / 2, n2 = N - n1, i, j, i1, j1, sols = 0; |
|||
return 0; |
|||
#define SHOW_ALL 1 |
|||
}</lang> |
|||
#define N1 (1 << n1) |
|||
#define N2 (1 << n2) |
|||
sum_t *l = mksums(em, n1, 0), |
|||
*r = mksums(em + n1, n2, n1); |
|||
{{output}}<pre>alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate escritoire exorcism fiat filmy flatworm mincemeat plugging speakeasy |
|||
void showmask(unsigned int mask) |
|||
...</pre> |
|||
{ |
|||
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}}== |
=={{header|D}}== |