bonanova Posted June 9, 2009 Report Share Posted June 9, 2009 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? Quote Link to comment Share on other sites More sharing options...
0 HoustonHokie Posted June 9, 2009 Report Share Posted June 9, 2009 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. Quote Link to comment Share on other sites More sharing options...
0 Wilson Posted June 9, 2009 Report Share Posted June 9, 2009 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 Quote Link to comment Share on other sites More sharing options...
0 Glycereine Posted June 9, 2009 Report Share Posted June 9, 2009 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. Quote Link to comment Share on other sites More sharing options...
0 Glycereine Posted June 9, 2009 Report Share Posted June 9, 2009 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 Quote Link to comment Share on other sites More sharing options...
0 Glycereine Posted June 9, 2009 Report Share Posted June 9, 2009 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. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 9, 2009 Report Share Posted June 9, 2009 18. does anyone know how many for 3 coins? Quote Link to comment Share on other sites More sharing options...
0 Glycereine Posted June 9, 2009 Report Share Posted June 9, 2009 13: 1-5,5+11n 1-6,6+13n 1-7,7+15n 1-8,8+17n 1-9,9+19n18. does anyone know how many for 3 coins? Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 9, 2009 Report Share Posted June 9, 2009 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. Quote Link to comment Share on other sites More sharing options...
0 Glycereine Posted June 9, 2009 Report Share Posted June 9, 2009 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! Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 9, 2009 Report Share Posted June 9, 2009 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 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 9, 2009 Report Share Posted June 9, 2009 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 Quote Link to comment Share on other sites More sharing options...
0 Glycereine Posted June 9, 2009 Report Share Posted June 9, 2009 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 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 9, 2009 Report Share Posted June 9, 2009 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) Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 9, 2009 Report Share Posted June 9, 2009 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 Quote Link to comment Share on other sites More sharing options...
0 EventHorizon Posted June 10, 2009 Report Share Posted June 10, 2009 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. Quote Link to comment Share on other sites More sharing options...
0 Glycereine Posted June 10, 2009 Report Share Posted June 10, 2009 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. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted June 10, 2009 Author Report Share Posted June 10, 2009 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. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 10, 2009 Report Share Posted June 10, 2009 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? Quote Link to comment Share on other sites More sharing options...
0 Glycereine Posted June 10, 2009 Report Share Posted June 10, 2009 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. Quote Link to comment Share on other sites More sharing options...
0 Prof. Templeton Posted June 10, 2009 Report Share Posted June 10, 2009 (edited) 16 different denominations. 1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50 Edited June 10, 2009 by Prof. Templeton Quote Link to comment Share on other sites More sharing options...
0 Glycereine Posted June 10, 2009 Report Share Posted June 10, 2009 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? Quote Link to comment Share on other sites More sharing options...
0 Prof. Templeton Posted June 10, 2009 Report Share Posted June 10, 2009 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, 52which gives their max of $1.04. I like the first one I posted better since it stops right at 1 dollar. Quote Link to comment Share on other sites More sharing options...
0 EventHorizon Posted June 17, 2009 Report Share Posted June 17, 2009 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> Quote Link to comment Share on other sites More sharing options...
0 EventHorizon Posted June 29, 2009 Report Share Posted June 29, 2009 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. Quote Link to comment Share on other sites More sharing options...
0 EventHorizon Posted June 30, 2009 Report Share Posted June 30, 2009 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> Quote Link to comment Share on other sites More sharing options...
Question
bonanova
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?
Link to comment
Share on other sites
25 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.