#include <stdio.h> // Brute Force All Combinations

511 23-1-03

class selection

{ protected:

int wanted[100];

int bestpattern[100];

int number;

public:

selection(int n)

{ number=n;

for (int i=0; i<=number; i+=1)

wanted[i]=0; }

void next(void)

{ int i=0;

while (wanted[i]==1)

{ wanted[i]=0;

i+=1; }

wanted[i]=1; }

bool finished(void)

{ return wanted[number]==1; }

int sum_of_selection(int weights[])

{ int sum=0;

for (int i=0; i<number; i+=1)

if (wanted[i])

sum+=weights[i];

return sum; }

void remember(void)

{ for (int i=0; i<number; i+=1)

bestpattern[i]=wanted[i]; }

int *answer(void)

{ return bestpattern; } };

void main(void)

{ int num, max;

printf("How many packages? ");

scanf("%d", &num);

printf("Maximum total weight? ");

scanf("%d", &max);

int wt[num];

for (int i=0; i<num; i+=1)

{ printf("Weight of package %d: ", i+1);

scanf("%d", &wt[i]); }

int bestsum = -1;

selection pattern(num);

while ( ! pattern.finished())

{ int thissum = pattern.sum_of_selection(wt);

if (thissum > bestsum && thissum <= max)

{ pattern.remember();

bestsum = thissum; }

pattern.next(); }

int *solution = pattern.answer();

printf("Best solution has total weight %d, take these packages:\n", bestsum);

for (int i=0; i<num; i+=1)

if (solution[i])

printf("%5d", i+1);

printf("\n");

for (int i=0; i<num; i+=1)

if (solution[i])

printf("%5d", wt[i]);

printf("\n"); }

Brute Force All Combinations

N	run 1	run 2	run 3	formula
...	...	...	...	...
9	0.000	0.000	0.000	0.000
10	0.001	0.000	0.000	0.001
...	...	...	...	...
...	...	...	...	...
18	0.133	0.141	0.133	0.158
19	0.281	0.273	0.289	0.316
20	0.586	0.594	0.586	0.632
21	1.219	1.219	1.227	1.265
22	2.531	2.516	2.547	2.531
23	5.289	5.242	5.227	5.062
24	10.844	10.852	10.867	10.124
...	...	...	...	...

time is in Seconds,

formula is 6.034´10^-7 ´ 2^N

Brute Force All Combinations

N	run 1	run 2	run 3	formula*
...	...	...	...	...
9	0.000	0.000	0.000	0.000
10	0.001	0.000	0.000	0.001
...	...	...	...	...
...	...	...	...	...
18	0.133	0.141	0.133	0.127
19	0.281	0.273	0.289	0.268
20	0.586	0.594	0.586	0.565
21	1.219	1.219	1.227	1.187
22	2.531	2.516	2.547	2.487
23	5.289	5.242	5.227	5.200
24	10.844	10.852	10.867	10.852
...	...	...	...	...

time is in Seconds,

formula* is 26.95´10^-9 ´ N´2^N