BrainDen.com - Brain Teasers
• 0

## Question

Recasting an old MG favorite:

In the U.S. if you wanted to produce \$.99, you'd need at least 8 coins;

\$.49 would require at least 7 coins, and so on. Yesterday our President

declared that the current coin denominations of 50, 25, 10, 5 and 1 do

not constitute Change you can believe in, and ordered a new set of coins

to be minted.

I believe that any citizen of this country should be able to produce any

amount of money less than one dollar using at most two coins, he said.

And he challenged his greatest group of thinkers, the Brain Denizens,

to establish a set of coins that accomplishs this feat.

How many coin denominations will required?

## Recommended Posts

• 0

Certainly if you had all the odd currencies from 1 cent to 49 cents as well as a 50-cent piece, you could do it. This would require 26 coins. But perhaps there's a better solution.

##### Share on other sites

• 0
Recasting an old MG favorite:

In the U.S. if you wanted to produce \$.99, you'd need at least 8 coins;

\$.49 would require at least 7 coins, and so on. Yesterday our President

declared that the current coin denominations of 50, 25, 10, 5 and 1 do

not constitute Change you can believe in, and ordered a new set of coins

to be minted.

I believe that any citizen of this country should be able to produce any

amount of money less than one dollar using at most two coins, he said.

And he challenged his greatest group of thinkers, the Brain Denizens,

to establish a set of coins that accomplishs this feat.

How many coin denominations will required?

Eighteen

##### Share on other sites

• 0

Could do it with every 10 and every 1 also.

So 1-9 and 10,20,30-90

Makes 18 coins.

Certainly if you had all the odd currencies from 1 cent to 49 cents as well as a 50-cent piece, you could do it. This would require 26 coins. But perhaps there's a better solution.
##### Share on other sites

• 0
Could do it with every 10 and every 1 also.

So 1-9 and 10,20,30-90

Makes 18 coins.

18 coins is the minimum but there are 3 ways it could be made (possibly more).

1,2,3,4,5,6,7,14,22,30,38,46,54,62,70,78,86,94

1,2,3,4,5,6,7,8,16,25,34,43,52,61,70,79,88,97

##### Share on other sites

• 0
Certainly if you had all the odd currencies from 1 cent to 49 cents as well as a 50-cent piece, you could do it. This would require 26 coins. But perhaps there's a better solution.

Also this solution wouldn't work for even numbers above 50 cents.

##### Share on other sites

• 0

18. does anyone know how many for 3 coins?

##### Share on other sites

• 0

13:

1-5,5+11n

1-6,6+13n

1-7,7+15n

1-8,8+17n

1-9,9+19n

18. does anyone know how many for 3 coins?
##### Share on other sites

• 0

I'm sure it is probably

18

But maybe if you try a different way..

Do it in 10 coins..

coins can represent up to 10 cents.

A coin that is 1-10 cents.

11-20

21-30

31-40

41-50

51-60

61-70

71-80

81-90

91-99 (only one with 9 values)

So if you want something for 45 cents, you give them the 41-50 cent coin, now they owe you up to 5 cents, so they give you a 1-10 cent coin back. Could work if everyone believed in the system.

##### Share on other sites

• 0
I'm sure it is probably

But maybe if you try a different way..

Do it in 10 coins..

coins can represent up to 10 cents.

A coin that is 1-10 cents.

11-20

21-30

31-40

41-50

51-60

61-70

71-80

81-90

91-99 (only one with 9 values)

So if you want something for 45 cents, you give them the 41-50 cent coin, now they owe you up to 5 cents, so they give you a 1-10 cent coin back. Could work if everyone believed in the system.

18

Genius!

##### Share on other sites

• 0
I'm sure it is probably

But maybe if you try a different way..

Do it in 10 coins..

coins can represent up to 10 cents.

A coin that is 1-10 cents.

11-20

21-30

31-40

41-50

51-60

61-70

71-80

81-90

91-99 (only one with 9 values)

So if you want something for 45 cents, you give them the 41-50 cent coin, now they owe you up to 5 cents, so they give you a 1-10 cent coin back. Could work if everyone believed in the system.

18

if you were to do it like that it could be 2 coins. 1-49 and 50-99 or one coin 1-99

##### Share on other sites

• 0
13:

1-5,5+11n

1-6,6+13n

1-7,7+15n

1-8,8+17n

1-9,9+19n

i dont get your math. i have 90,80,70,60,50,40,30,20,10,5,4,3,2,1

14 coins

##### Share on other sites

• 0
i dont get your math. i have 90,80,70,60,50,40,30,20,10,5,4,3,2,1

14 coins

13:

1,2,3,4,5,16,27,38,49,60,71,82,93

1,2,3,4,5,6,19,32,45,58,71,84,97

1,2,3,4,5,6,7,22,37,52,67,82,97

1,2,3,4,5,6,7,8,25,42,59,76,93

1,2,3,4,5,6,7,8,9,28,47,66,85

##### Share on other sites

• 0
13:

1,2,3,4,5,16,27,38,49,60,71,82,93

1,2,3,4,5,6,19,32,45,58,71,84,97

1,2,3,4,5,6,7,22,37,52,67,82,97

1,2,3,4,5,6,7,8,25,42,59,76,93

1,2,3,4,5,6,7,8,9,28,47,66,85

For your first set you can't make 13-15 in 3 coins...

For your second set you can't make 16-18 in 3 coins...

For your third set you can't make 18-21 in 3 coins...

For your forth set you can't make 22-24 in 3 coins...

and your fifth set you can't make 25-27 in 3 coins...

I'm goin' w/ 14 coins for sets of 3...(the 1-5, and then by 10's as stated above)

##### Share on other sites

• 0
13:

1,2,3,4,5,16,27,38,49,60,71,82,93

1,2,3,4,5,6,19,32,45,58,71,84,97

1,2,3,4,5,6,7,22,37,52,67,82,97

1,2,3,4,5,6,7,8,25,42,59,76,93

1,2,3,4,5,6,7,8,9,28,47,66,85

yup 13. thanks man

##### Share on other sites

• 0
yup 13. thanks man

If you only allow 2 coins, then the set {1 2 3 4 8 13 16} can get up to 21.

{1,2,3,4,4+1,4+2,4+3,8,8+1,8+2,8+3,8+4,13,13+1,13+2,16,16+1,16+2,16+3,16+4,13+8}

Using this same set but allowing 3 coins allows up to 37.

{...,13+8+1,13+8+2,13+8+3,13+8+4,16+8+2,16+8+3,16+8+4,13+16,13+16+1,13+16+2,13+1

6+3,13+16+4,16+16+2,16+16+3,16+16+4,16+13+8}

So now we can add 38, 60, and 82. Since these are each separated by 22 we can use the 2 coin combinations above to reach between them.

So my final set is {1,2,3,4,8,13,16,38,60,82}, which only has 10 elements.

##### Share on other sites

• 0
For your first set you can't make 13-15 in 3 coins...

For your second set you can't make 16-18 in 3 coins...

For your third set you can't make 18-21 in 3 coins...

For your forth set you can't make 22-24 in 3 coins...

and your fifth set you can't make 25-27 in 3 coins...

I'm goin' w/ 14 coins for sets of 3...(the 1-5, and then by 10's as stated above)

Look closer all my combo's work. However look below you can do it in less:

If you only allow 2 coins, then the set {1 2 3 4 8 13 16} can get up to 21.

{1,2,3,4,4+1,4+2,4+3,8,8+1,8+2,8+3,8+4,13,13+1,13+2,16,16+1,16+2,16+3,16+4,13+8}

Using this same set but allowing 3 coins allows up to 37.

{...,13+8+1,13+8+2,13+8+3,13+8+4,16+8+2,16+8+3,16+8+4,13+16,13+16+1,13+16+2,13+1

6+3,13+16+4,16+16+2,16+16+3,16+16+4,16+13+8}

So now we can add 38, 60, and 82. Since these are each separated by 22 we can use the 2 coin combinations above to reach between them.

So my final set is {1,2,3,4,8,13,16,38,60,82}, which only has 10 elements.

Awesome! You're right as far as I can tell! Makes me wonder if it can be less though.

##### Share on other sites

• 0

As the President looked over the evening mail he was heard to exclaim:

Eighteen? Are you kidding me? Dick Cheney gave me 18!

The best he got was 1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90.

No one can do better?

The two coins don't have to have different values.

##### Share on other sites

• 0
As the President looked over the evening mail he was heard to exclaim:

Eighteen? Are you kidding me? Dick Cheney gave me 18!

The best he got was 1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90.

No one can do better?

The two coins don't have to have different values.

If by 2 coins he means 2 different coins, but however many of each, I'll say a penny and a dime. You can make any change with a penny and a dime. Or a penny and nickel too I suppose. Or just mint pennies only.

A simpler version of my earlier post...

Use 9 coins:

On the heads side call each one 1cent,2cents...9cents.

On the tails side call it 10cents,20cents...,90cents.

So you could make any change using 2 coins depending on which side is showing.(I think George Bush just might fall for this. (No offense George Bush) )

I don't know...18?
##### Share on other sites

• 0
As the President looked over the evening mail he was heard to exclaim:

Eighteen? Are you kidding me? Dick Cheney gave me 18!

The best he got was 1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90.

No one can do better?

The two coins don't have to have different values.

I can make many other combinations that work for 18 coins but have yet to find one smaller. I don't doubt it exists but it's escaping me.

##### Share on other sites

• 0

16 different denominations.

1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50

Edited by Prof. Templeton
##### Share on other sites

• 0
16 different denominations.

1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50

I see it but how on earth did you come up with it?

##### Share on other sites

• 0
I see it but how on earth did you come up with it?

Sloane's told me the minimum number of denominations was 16. With 16 demoninations you can obtain a value of \$1.04. Starting with their solution for 20 denominations as a base, another set would be

Spoiler for this:

1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 47, 48, 49, 51, 52
which gives their max of \$1.04. I like the first one I posted better since it stops right at 1 dollar.
##### Share on other sites

• 0

I wrote some code (included below), and used it to verify that there is no 15 coin solution. I then made it work for more than 2 coins, and here are the results (including the "best" solution... the one that allows combining to reach all numbers up to a highest maximum):

2: 16 denominations. Still running, and I don't expect it to finish this week.

3: 9 denominations == 1 3 8 9 14 32 36 51 53 (up to 121) Computed in 4787 seconds.

4: 6 denominations == 1 4 9 16 38 49 (up to 108). Computed in 20 seconds.

5: 5 denominations == 1 4 9 31 51 (up to 126). Computed in 3 seconds.

6: 4 denominations == 1 4 19 33 (up to 114). Computed in under a second.

7: 4 denominations == 1 5 24 37 (up to 165). Computed in 4 seconds.

8: 4 denominations == 1 6 25 65 (up to 234). Computed in 30 seconds.

9: 3 denominations == 1 9 20 (up to 112). Computed in under a second.

10: 3 denominations == 1 10 26 (up to 146). Computed in under a second.

#include <iostream>
#include <windows.h>
#include <winbase.h>
#include <time.h>

using namespace std;

//////////////////////these are the variables to play with
//max number of coins to add together
int maxnum = 2;
//max target value
int maxt = 99;
//////////////////////

//amount to sleep each second (in milliseconds) -- to control cpu% used
#define sleepamount 400
//max number of denominations to test
#define maxcoins 50

int coins[maxcoins];//denomiation values
int numcoins=0; // one less than the first number of denominations you want to check
int stack[50];//used to check all combinations of denominations
int totals[50];
int best[maxcoins];//store the best set found
int bestscore = 0;

int main(int argc, char* argv[])
{
if (argc>1) maxt = atoi(argv[1]);
if (argc>2) maxnum = atoi(argv[2]);
if (argc>3) numcoins = atoi(argv[3])-1;

memset(best,0,sizeof(int)*maxcoins);
int done = 0;
int starttime = (int)time(0);
int lasttime = starttime;

while(!done)
{
numcoins++;
if (numcoins > maxcoins) break;
cout << "Testing " << numcoins << " coins." << endl;
for(int i = 0; i < numcoins; i++) coins[i] = i+1;
int next = maxt;
for(int i = numcoins-1; i >= 0; i--)//make sure large target values can be reached
{
if (coins[i] < (next+maxnum-1)/maxnum)
{
coins[i] = (next+maxnum-1)/maxnum;
next = coins[i];
}
else break;
}
if (coins[0] != 1) cout << "Target max definitely not reachable." << endl;

while(coins[0] == 1)//smallest denomination must be 1
{
if ((int)time(0)!=lasttime){Sleep(sleepamount);lasttime = (int)time(0);}

///check each target value up to maxt
int target=0;
while(1)
{
target++;
//try all combinations of coins to reach the target
int last = numcoins-1;
while(coins[last]>target)last--;
if (coins[last]==target)continue;
int foundtarget = 0;
int depth = 0;
stack[0] = -1;
while(depth >= 0)
{
stack[depth]++;
if (stack[depth]>last) {depth--; continue;}
int total = 0;
if (depth) total = totals[depth-1];
totals[depth] = total+coins[stack[depth]];
if (totals[depth]==target) {foundtarget = 1; break;}
if (totals[depth] > target) {depth--; continue;}
if (depth < maxnum-1) {depth++; stack[depth]=-1;}
}
if (!foundtarget) break;
}

if (target-1 > bestscore)
{
memcpy(best,coins,sizeof(int)*numcoins);
bestscore = target-1;
}

if (target >= maxt+1)
{
cout << endl;
for(int i = 0; i < numcoins; i++) cout << coins[i] << " ";
cout << " (up to " << target-1 << ") ";
done = 1;
//break; //add in this break to stop when first answer is found
}

///increment denominations
int index = numcoins-1;
while(coins[index] >= target) index--;
while(index && (coins[index]>=coins[index-1]*maxnum+1)) index--;
while(index && (coins[index]>=maxt-((numcoins-1)-index))) index--;
coins[index]++;
for(int i = index+1; i < numcoins; i++) coins[i] = coins[i-1]+1;
next = maxt;

for(int i = numcoins-1; i >= 0; i--)//make sure the large target values can be reached
{
if (coins[i] < (next+maxnum-1)/maxnum)
{
coins[i] = (next+maxnum-1)/maxnum;
next = coins[i];
}
else break;
}

//stuff to let me know it's still working
if ((index < numcoins-6)&&(!done)) cout << index << ",";
if ((index < numcoins-8)&&(!done)) cout << endl << "Time elapsed = " << ((int)time(0))-starttime << endl;
}
if (bestscore)
{
cout << endl << "Best for " << numcoins << " was " << bestscore << " = ";
for(int i = 0; i < numcoins; i++) cout << best[i] << " ";
cout << endl << endl;
}
//break;//remove this break to keep adding to the number of denominations until an answer is found
}
int endtime = (int)time(0);
cout << endl << "Finished in " << endtime-starttime << " seconds" << endl;
system("pause");
return 0;
}
`#include <stdio.h>`

##### Share on other sites

• 0
I wrote some code (included below), and used it to verify that there is no 15 coin solution. I then made it work for more than 2 coins, and here are the results (including the "best" solution... the one that allows combining to reach all numbers up to a highest maximum):

2: 16 denominations. Still running, and I don't expect it to finish this week.

3: 9 denominations == 1 3 8 9 14 32 36 51 53 (up to 121) Computed in 4787 seconds.

4: 6 denominations == 1 4 9 16 38 49 (up to 108). Computed in 20 seconds.

5: 5 denominations == 1 4 9 31 51 (up to 126). Computed in 3 seconds.

6: 4 denominations == 1 4 19 33 (up to 114). Computed in under a second.

7: 4 denominations == 1 5 24 37 (up to 165). Computed in 4 seconds.

8: 4 denominations == 1 6 25 65 (up to 234). Computed in 30 seconds.

9: 3 denominations == 1 9 20 (up to 112). Computed in under a second.

10: 3 denominations == 1 10 26 (up to 146). Computed in under a second.

#include <iostream>
#include <windows.h>
#include <winbase.h>
#include <time.h>

using namespace std;

//////////////////////these are the variables to play with
//max number of coins to add together
int maxnum = 2;
//max target value
int maxt = 99;
//////////////////////

//amount to sleep each second (in milliseconds) -- to control cpu% used
#define sleepamount 400
//max number of denominations to test
#define maxcoins 50

int coins[maxcoins];//denomiation values
int numcoins=0; // one less than the first number of denominations you want to check
int stack[50];//used to check all combinations of denominations
int totals[50];
int best[maxcoins];//store the best set found
int bestscore = 0;

int main(int argc, char* argv[])
{
if (argc>1) maxt = atoi(argv[1]);
if (argc>2) maxnum = atoi(argv[2]);
if (argc>3) numcoins = atoi(argv[3])-1;

memset(best,0,sizeof(int)*maxcoins);
int done = 0;
int starttime = (int)time(0);
int lasttime = starttime;

while(!done)
{
numcoins++;
if (numcoins > maxcoins) break;
cout << "Testing " << numcoins << " coins." << endl;
for(int i = 0; i < numcoins; i++) coins[i] = i+1;
int next = maxt;
for(int i = numcoins-1; i >= 0; i--)//make sure large target values can be reached
{
if (coins[i] < (next+maxnum-1)/maxnum)
{
coins[i] = (next+maxnum-1)/maxnum;
next = coins[i];
}
else break;
}
if (coins[0] != 1) cout << "Target max definitely not reachable." << endl;

while(coins[0] == 1)//smallest denomination must be 1
{
if ((int)time(0)!=lasttime){Sleep(sleepamount);lasttime = (int)time(0);}

///check each target value up to maxt
int target=0;
while(1)
{
target++;
//try all combinations of coins to reach the target
int last = numcoins-1;
while(coins[last]>target)last--;
if (coins[last]==target)continue;
int foundtarget = 0;
int depth = 0;
stack[0] = -1;
while(depth >= 0)
{
stack[depth]++;
if (stack[depth]>last) {depth--; continue;}
int total = 0;
if (depth) total = totals[depth-1];
totals[depth] = total+coins[stack[depth]];
if (totals[depth]==target) {foundtarget = 1; break;}
if (totals[depth] > target) {depth--; continue;}
if (depth < maxnum-1) {depth++; stack[depth]=-1;}
}
if (!foundtarget) break;
}

if (target-1 > bestscore)
{
memcpy(best,coins,sizeof(int)*numcoins);
bestscore = target-1;
}

if (target >= maxt+1)
{
cout << endl;
for(int i = 0; i < numcoins; i++) cout << coins[i] << " ";
cout << " (up to " << target-1 << ") ";
done = 1;
//break; //add in this break to stop when first answer is found
}

///increment denominations
int index = numcoins-1;
while(coins[index] >= target) index--;
while(index && (coins[index]>=coins[index-1]*maxnum+1)) index--;
while(index && (coins[index]>=maxt-((numcoins-1)-index))) index--;
coins[index]++;
for(int i = index+1; i < numcoins; i++) coins[i] = coins[i-1]+1;
next = maxt;

for(int i = numcoins-1; i >= 0; i--)//make sure the large target values can be reached
{
if (coins[i] < (next+maxnum-1)/maxnum)
{
coins[i] = (next+maxnum-1)/maxnum;
next = coins[i];
}
else break;
}

//stuff to let me know it's still working
if ((index < numcoins-6)&&(!done)) cout << index << ",";
if ((index < numcoins-8)&&(!done)) cout << endl << "Time elapsed = " << ((int)time(0))-starttime << endl;
}
if (bestscore)
{
cout << endl << "Best for " << numcoins << " was " << bestscore << " = ";
for(int i = 0; i < numcoins; i++) cout << best[i] << " ";
cout << endl << endl;
}
//break;//remove this break to keep adding to the number of denominations until an answer is found
}
int endtime = (int)time(0);
cout << endl << "Finished in " << endtime-starttime << " seconds" << endl;
system("pause");
return 0;
}
`#include <stdio.h>`

All possible solutions to the original problem are the following:

1 2 3 7 11 15 19 23 27 28 29 30 60 63 66 69 (up to 99)

1 2 3 7 11 15 19 23 27 28 29 30 61 64 67 70 (up to 100)

1 3 4 5 8 14 20 26 32 35 41 45 46 48 49 53 (up to 99)

1 3 4 5 8 14 20 26 32 38 41 43 46 47 48 51 (up to 99)

1 3 4 5 8 14 20 26 32 38 41 45 46 48 49 85 (up to 99)

1 3 4 5 8 14 20 26 32 38 43 44 46 47 48 51 (up to 99)

1 3 4 5 8 14 20 26 32 38 44 45 47 48 49 52 (up to 101)

1 3 4 5 8 14 20 26 32 38 44 46 47 48 49 51 (up to 100)

1 3 4 5 8 14 20 26 32 38 44 46 48 49 51 53 (up to 102)

1 3 4 5 8 14 20 26 32 38 44 47 48 49 51 52 (up to 104) **best one

1 3 4 6 10 14 18 22 26 28 29 31 61 62 67 68 (up to 99)

1 3 4 7 8 9 16 17 21 24 35 46 57 68 79 90 (up to 100)

1 3 4 9 11 16 20 25 30 34 39 41 46 47 49 50 (up to 100)

1 3 5 6 10 14 18 22 26 28 29 31 61 62 67 68 (up to 99)

It took 1106776 seconds (12.8 days) to finish.

##### Share on other sites

• 0

Not sure anyone is interested... but here it is anyway.

what took my old version 4787 seconds (solving the 3 coin problem), now takes 891 seconds. So perhaps solving the 2 coin problem will only take 3 days instead of 2 weeks.

#include <iostream>
#include <windows.h>
#include <winbase.h>
#include <time.h>

using namespace std;

//////////////////////these are the variables to play with
//max number of coins to add together
int maxnum = 2;
//max target value
int maxt = 99;
//////////////////////

//amount to sleep each second (in milliseconds) -- to control cpu% used
#define sleepamount 400
//max number of denominations to test
#define maxcoins 50

int coins[maxcoins];//denomiation values
int numcoins=0; // one less than the first number of denominations you want to check
int stack[50];//used to check all combinations of denominations
int totals[50];
int best[maxcoins];//store the best set found
int bestscore = 0;
int lastindex = 1;
int startt[maxcoins];

int main(int argc, char* argv[])
{
if (argc>1) maxt = atoi(argv[1]);
if (argc>2) maxnum = atoi(argv[2]);
if (argc>3) numcoins = atoi(argv[3])-1;

memset(best,0,sizeof(int)*maxcoins);
int done = 0;
int starttime = (int)time(0);
int lasttime = starttime;

startt[0] = maxnum;
lastindex = 1;
while(!done)
{
numcoins++;
if (numcoins > maxcoins) break;
cout << "Testing " << numcoins << " coins." << endl;
for(int i = 0; i < numcoins; i++) coins[i] = i+1;
int next = maxt;
for(int i = numcoins-1; i >= 0; i--)//make sure large target values can be reached
{
if (coins[i] < (next+maxnum-1)/maxnum)
{
coins[i] = (next+maxnum-1)/maxnum;
next = coins[i];
}
else break;
}
if (coins[0] != 1) cout << "Target max definitely not reachable." << endl;

int target;
while(coins[0] == 1)//smallest denomination must be 1
{
if ((int)time(0)!=lasttime){Sleep(sleepamount);lasttime = (int)time(0);}

///check each target value up to maxt

target=startt[lastindex-1];
int tochange = lastindex;
while(1)
{
target++;
//try all combinations of coins to reach the target
int last = numcoins-1;
while(coins[last]>target)last--;
//if (coins[last]==target)continue;
int foundtarget = 0;
int depth = 0;
stack[0] = -1;
while(depth >= 0)
{
stack[depth]++;
int total = 0;
if (depth)
{
if (stack[depth]>stack[depth-1]) {depth--; continue;}
total = totals[depth-1];
}
else
{
if (stack[depth]>last) {depth--; continue;}
}
totals[depth] = total+coins[stack[depth]];
if (totals[depth]==target) {foundtarget = 1; break;}
if (totals[depth] > target) {depth--; continue;}
if (depth < maxnum-1) {depth++; stack[depth]=-1;}
}

if (!foundtarget)
{
while (tochange < numcoins)
{
startt[tochange++] = target-1;
}
break;
}
else
{
while (stack[0] > tochange)
{
startt[tochange++] = target-1;
}
}
}

if (target-1 > bestscore)
{
memcpy(best,coins,sizeof(int)*numcoins);
bestscore = target-1;
}

if (target >= maxt+1)
{
cout << endl;
for(int i = 0; i < numcoins; i++) cout << coins[i] << " ";
cout << " (up to " << target-1 << ") ";
done = 1;
//break; //add in this break to stop when first answer is found
}

///increment denominations
int index = numcoins-1;
while(coins[index] >= target) index--;
while(index && (coins[index]>=coins[index-1]*maxnum+1)) index--;
while(index && (coins[index]>=maxt-((numcoins-1)-index))) index--;
lastindex = index;
coins[index]++;
for(int i = index+1; i < numcoins; i++) coins[i] = coins[i-1]+1;
next = maxt;

for(int i = numcoins-1; i >= 0; i--)//make sure the large target values can be reached
{
if (coins[i] < (next+maxnum-1)/maxnum)
{
coins[i] = (next+maxnum-1)/maxnum;
next = coins[i];
}
else break;
}

//stuff to let me know it's still working
if ((index < numcoins-6)&&(!done)) cout << index << ",";
if ((index < numcoins-8)&&(!done)) cout << endl << "Time elapsed = " << ((int)time(0))-starttime << endl;
}
if (bestscore)
{
cout << endl << "Best for " << numcoins << " was " << bestscore << " = ";
for(int i = 0; i < numcoins; i++) cout << best[i] << " ";
cout << endl << endl;
}
//break;//remove this break to keep adding to the number of denominations until an answer is found
}
int endtime = (int)time(0);
cout << endl << "Finished in " << endtime-starttime << " seconds" << endl;
system("pause");
return 0;
}
`#include <stdio.h>`

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.