Re: Optimize lisp program

OK, here you go. I doubt that you will have any speed problems with the
program below. What about a larger test?

Nicolas

(defstruct (coin (:type list))
price
weight)

(defun solve-piggy-bank (target-weight coins)
(let ((minimal-amount (make-array (1+ target-weight)
:initial-element nil)))
(setf (aref minimal-amount 0) 0)
(loop for weight from 0 upto target-weight
and amount across minimal-amount
when amount do
(loop for coin in coins
for new-weight = (+ weight (coin-weight coin))
and new-amount = (+ amount (coin-price coin))
when (<= new-weight target-weight) do
(let ((old-amount (aref minimal-amount new-weight)))
(when (or (null old-amount)
(> old-amount new-amount))
(setf (aref minimal-amount new-weight) new-amount)))))
(let ((amount (aref minimal-amount target-weight)))
(if amount
(format t "Minimal amount: ~A~%" amount)
(format t "Impossible!~%")))))

(solve-piggy-bank 31 '((2 3) (7 5)))

.

Relevant Pages

  • Re: Optimize lisp program
    ... (defstruct (coin (:type list)) ... and amount across minimal-amount ... (when (or (null old-amount) ... (setf (aref minimal-amount new-weight) ...
    (comp.lang.lisp)
  • Re: Making Change (#154)
    ... it is not necessary to sort the input array of coins (when the input ... in every matrixcell report the integer part and the rest of the ... the number of coin, number_of_coins that will be used to compute the ... a "n,0" cell.value case, we have to now what amount we are processing, ...
    (comp.lang.ruby)
  • Re: pay a motoring fine, get the bomb squad out
    ... know what the amount for 10Ps is ... There is nothing that determines that any amount of coin is legal, ... There is a limit as to what constitutes legal tender, ... If someone wants accept an offer of payment in chickens, ...
    (uk.transport)
  • Re: Cashier Balance Sheet
    ... You can get it to work in the example given by rounding each coin down to the ... If a1 has the till amount of pennies, the amount to keep is: ... list each denomination of coin and bill. ... The bank amount is $250.00. ...
    (microsoft.public.excel.worksheet.functions)