I banged out a brute-force iterative solution pretty quickly in C. It's not general, but could be made so pretty easily. #define NUM_COINS 5 #define GOAL_IN_CENTS 100 unsigned char ucCoinVal[] = { 1, 5, 10, 25, 50 }; unsigned char isGoodSet( unsigned char aucCoins[] ); int main( void ) { int i; unsigned char max[NUM_COINS]; unsigned char aucCoins[NUM_COINS]; int iTotal = 0; for ( i = 0; i < NUM_COINS; i++ ) { max[i] = GOAL_IN_CENTS / ucCoinVal[i]; printf( "\nCoin %3d cents has max %3d for goal", ucCoinVal[i], max[i] ); } printf( "\n" ); for ( aucCoins[0] = 0; aucCoins[0] <= max[0]; aucCoins[0]++ ) { for ( aucCoins[1] = 0; aucCoins[1] <= max[1]; aucCoins[1]++ ) { for ( aucCoins[2] = 0; aucCoins[2] <= max[2]; aucCoins[2]++ ) { for ( aucCoins[3] = 0; aucCoins[3] <= max[3]; aucCoins[3]++ ) { for ( aucCoins[4] = 0; aucCoins[4] <= max[4]; aucCoins[4]++ ) { if ( isGoodSet( aucCoins ) ) { iTotal++; printf( "\nGood set : %3d %3d %3d %3d %3d", aucCoins[0], aucCoins[1], aucCoins[2], aucCoins[3], aucCoins[4] ); } } } } } } printf( "\nFound %d solutions.\n", iTotal ); } // Function to determine if we have a good set of coins (adds up to the goal). unsigned char isGoodSet( unsigned char aucCoins[] ) { int i; int iSum = 0; for ( i = 0; i < NUM_COINS; i++ ) { iSum += ( aucCoins[i] * ucCoinVal[i] ); } return ( iSum == GOAL_IN_CENTS ) ? 1 : 0; } #include <stdio.h>
Nonsense! The rule is always, "Get it working first, then optimise - but only if necessary!" But there are several simple optimisations possible, I freely admit :-)
Note - in the centre of the loops, markup has swallowed my increment operator - should be "iTotal ++;" Same story for all the for-loop incrementors. There may be other manglings I haven't noticed. [edit] I've fixed up the missing "++" operators - let me know if you notice any other manglings.
hubski's markdown implementation is really bad for posting code because it still parses what's inside the code rather than outputting it verbatim. You STILL have to escape special symbols ilke + inside code too. It's very frustrating.
mk forwardslash rob05c -- regarding our conversation regarding markdown
Agreed - not great for code, or for poetry / song-lyrics. I had to bung in two spaces at the front of every line to convince it to use a monospace font. There ought to be a way to say "don't format this text at all please".
Here's the output (or run it yourself, if you have gcc) : Coin 5 cents has max 20 for goal Coin 10 cents has max 10 for goal Coin 25 cents has max 4 for goal Coin 50 cents has max 2 for goal Good set : 0 0 0 0 2 Good set : 0 0 0 2 1 Good set : 0 0 0 4 0 Good set : 0 0 5 0 1 Good set : 0 0 5 2 0 Good set : 0 0 10 0 0 Good set : 0 1 2 1 1 Good set : 0 1 2 3 0 Good set : 0 1 7 1 0 Good set : 0 2 4 0 1 Good set : 0 2 4 2 0 Good set : 0 2 9 0 0 Good set : 0 3 1 1 1 Good set : 0 3 1 3 0 Good set : 0 3 6 1 0 Good set : 0 4 3 0 1 Good set : 0 4 3 2 0 Good set : 0 4 8 0 0 Good set : 0 5 0 1 1 Good set : 0 5 0 3 0 Good set : 0 5 5 1 0 Good set : 0 6 2 0 1 Good set : 0 6 2 2 0 Good set : 0 6 7 0 0 Good set : 0 7 4 1 0 Good set : 0 8 1 0 1 Good set : 0 8 1 2 0 Good set : 0 8 6 0 0 Good set : 0 9 3 1 0 Good set : 0 10 0 0 1 Good set : 0 10 0 2 0 Good set : 0 10 5 0 0 Good set : 0 11 2 1 0 Good set : 0 12 4 0 0 Good set : 0 13 1 1 0 Good set : 0 14 3 0 0 Good set : 0 15 0 1 0 Good set : 0 16 2 0 0 Good set : 0 18 1 0 0 Good set : 0 20 0 0 0 Good set : 5 0 2 1 1 Good set : 5 0 2 3 0 Good set : 5 0 7 1 0 Good set : 5 1 4 0 1 Good set : 5 1 4 2 0 Good set : 5 1 9 0 0 Good set : 5 2 1 1 1 Good set : 5 2 1 3 0 Good set : 5 2 6 1 0 Good set : 5 3 3 0 1 Good set : 5 3 3 2 0 Good set : 5 3 8 0 0 Good set : 5 4 0 1 1 Good set : 5 4 0 3 0 Good set : 5 4 5 1 0 Good set : 5 5 2 0 1 Good set : 5 5 2 2 0 Good set : 5 5 7 0 0 Good set : 5 6 4 1 0 Good set : 5 7 1 0 1 Good set : 5 7 1 2 0 Good set : 5 7 6 0 0 Good set : 5 8 3 1 0 Good set : 5 9 0 0 1 Good set : 5 9 0 2 0 Good set : 5 9 5 0 0 Good set : 5 10 2 1 0 Good set : 5 11 4 0 0 Good set : 5 12 1 1 0 Good set : 5 13 3 0 0 Good set : 5 14 0 1 0 Good set : 5 15 2 0 0 Good set : 5 17 1 0 0 Good set : 5 19 0 0 0 Good set : 10 0 4 0 1 Good set : 10 0 4 2 0 Good set : 10 0 9 0 0 Good set : 10 1 1 1 1 Good set : 10 1 1 3 0 Good set : 10 1 6 1 0 Good set : 10 2 3 0 1 Good set : 10 2 3 2 0 Good set : 10 2 8 0 0 Good set : 10 3 0 1 1 Good set : 10 3 0 3 0 Good set : 10 3 5 1 0 Good set : 10 4 2 0 1 Good set : 10 4 2 2 0 Good set : 10 4 7 0 0 Good set : 10 5 4 1 0 Good set : 10 6 1 0 1 Good set : 10 6 1 2 0 Good set : 10 6 6 0 0 Good set : 10 7 3 1 0 Good set : 10 8 0 0 1 Good set : 10 8 0 2 0 Good set : 10 8 5 0 0 Good set : 10 9 2 1 0 Good set : 10 10 4 0 0 Good set : 10 11 1 1 0 Good set : 10 12 3 0 0 Good set : 10 13 0 1 0 Good set : 10 14 2 0 0 Good set : 10 16 1 0 0 Good set : 10 18 0 0 0 Good set : 15 0 1 1 1 Good set : 15 0 1 3 0 Good set : 15 0 6 1 0 Good set : 15 1 3 0 1 Good set : 15 1 3 2 0 Good set : 15 1 8 0 0 Good set : 15 2 0 1 1 Good set : 15 2 0 3 0 Good set : 15 2 5 1 0Coin 1 cents has max 100 for goal