LispForum

You can view the process of making changes as recursive. You first see if any dollars are required, subtract them from the total, and then make change for what remains. The following function implements such a recursive approach to making change. The function make-change converts a given number of cents into dollars, half-dollars, quarters, and so forth.

Complete the LISP program to achieve the above requirements:

(defun make-change (money)
(cond ((>= money 100)
(cons (list (truncate money 100) 'dollars)
(make-change (rem money 100))))
((>= money 25)
(cons ….

The use of above function is:
> (make-change 123)
((1 DOLLARS) (2 DIMES) (3 CENTS))

You could makeAnd then you feed the function a list, starting with the higher-value coins ending with the lower value coins, and then go down that list with a recursive function, each time seeing how many coins/bills you can use with (floor money (coin-value top-of-the-list)), subtracting the associated value from the total amount, and then doing the same with the other types of money.

Your approach seems like it would work, but if i were you i'd prefer something with the values and coins not so hard-coded in. Also in the forum please use \[code\] tags, and indent.(Indentation is also good for clarity as you read your own code..)

I actually did this yesterday. I wanted to run a genetic algorithm to see what set of 'coins denominations' made for the least amount of change. Anyway, here was mine:
See, 10 is 3 3-unit coins, 0 2-unit coins and 1 1-unit coin.

Warren Wilkinson wrote:I actually did this yesterday. I wanted to run a genetic algorithm to see what set of 'coins denominations' made for the least amount of change.

Come up with anything interesting?

Well, not anything too interesting. The results are highly dependent on the heuristic for deciding 'best'. For example, a set of coins that had denominations for 1, 2, 3, 4, 5, 6 ... , 97, 98, 99, 100 would perform well -- only 1 coin is ever needed. If you add a cost for the number of unique coins, you get different results depending on that cost.

For a cost of (+ ( expt 1.85 num-coins ) average-number-of-coins-needed) the best candidates were:

• 30 5 1
• 16 3 1
• 25 5 1

For a cost of (+ (expt 1.35 num-coins) average-number-of-coins-needed) the best candidates were

• 47 13 5 1, (score 6.74)
• 27 13 5 1, (score 6.83)
• 27 7 5 1, (score 6.86)

By comparison 25, 10, 5, 1 scored 7.14

These results also depend on the amount of change you are making. If you are trying to find the most efficient ways to make change up to 10 dollars worth, the numbers become around 3010, 1145, 313, 64, 10, 1.

In my case, I wanted Starcraft 2 players to be able to write 'cheque -number-' and spawn a unit with that many 'amount' buffs on it. The problem was that applying 6000 1+amount buffs to a unit caused the game to pause, but applying 6 1000+amount buffs was quick. So I wanted to design the best set of buff amounts to make any number the user typed quickly applied. I assumed most users would type human numbers like 300, 6000 25000, &c and only rarely have strange numbers like 31567. Under these circumstances power of tens buffs were by far the best performer.