どうかく？の問題
んー、今のレベルじゃ難しい…
(require :iterate) (in-package :iterate) (defparameter *coins* '(500 100 50 10 5 1)) ;; DRY *coins* (defun combinations (wallet) (labels ((cnt (coin) (or (cdr (assoc coin wallet)) 0))) (iter (for c0 from 0 to (cnt 500)) (appending (iter (for c1 from 0 to (cnt 100)) (appending (iter (for c2 from 0 to (cnt 50)) (appending (iter (for c3 from 0 to (cnt 10)) (appending (iter (for c4 from 0 to (cnt 5)) (appending (iter (for c5 from 0 to (cnt 1)) (collecting (delete-if (lambda (cons) (zerop (cdr cons))) `((500 . ,c0) (100 . ,c1) (50 . ,c2) (10 . ,c3) (5 . ,c4) (1 . ,c5))))))))))))))))) (combinations '((5 . 1) (1 . 1))) ; => (NIL ((1 . 1)) ((5 . 1)) ((5 . 1) (1 . 1))) ;; (amount '((5 . 1) (1 . 1))) ; => 6 (defun amount (wallet) (iter (for (coin . cnt) in wallet) (sum (* coin cnt)))) (defun change (amount) (iter (for coin in *coins*) (with cnt) (unless (zerop (setf cnt (floor (/ amount coin)))) (decf amount (* coin cnt)) (collect (cons coin cnt))))) ;; (change 121) ;; (change 687) (defun ways-to-pay (amount wallet) (let (changed-coins) (iter (for combination in (combinations wallet)) (if (let ((change-amount (- (amount combination) amount))) (and (<= 0 change-amount) (iter (for (c-coin . c-cnt) in (setf changed-coins (change change-amount))) (always (null (assoc c-coin combination)))))) (collect (list :pay combination :change changed-coins)))))) ;; (ways-to-pay 101 '((500 . 1) (100 . 2) (1 . 5))) ;; (combinations '((500 . 1) (100 . 2) (1 . 5))) (defun count-coins (wallet) (iter (for (coin . cnt) in wallet) (sum cnt))) ;; (setq wallet '((500 . 1) (100 . 2) (10 . 1))) ;; (count-coins wallet) ;; wallet: alist (defun pay (amount wallet) (iter (with coins-in-wallet = (count-coins wallet)) (for way in (ways-to-pay amount wallet)) (finding way minimizing (+ (- coins-in-wallet (count-coins (getf way :pay))) (count-coins (getf way :change))) into min) (finally (return (getf min :pay))))) (pay 147 '((1 . 2) (10 . 4) (100 . 3))) ; => ((100 . 2) (1 . 2))
