CommonLispで動的計画法

GWの前半は「プログラミングコンテストチャレンジブック」に捧げたのでその時の知見をブログにまとめていこうと思う。(3記事目)


問題文:

価値が vi 重さが wi であるような N 個の品物と、容量が W のナップザックがあります。次の条件を満たすように、品物を選んでナップザックに入れます:

選んだ品物の価値の合計をできるだけ高くする。
選んだ品物の重さの総和は W を超えない。
価値の合計の最大値を求めてください。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp


動的計画法を CommonLisp で実装するとこうなる:

(defun memo (fn)
    (let ((table (make-hash-table :test 'equal)))
        #'(lambda (&rest rest)
              (multiple-value-bind (val found-p) (gethash rest table)
                  (if found-p
                      val
                      (setf (gethash rest table) (apply fn rest)))))))

(defun memoize (fn-name)
    (setf (symbol-function fn-name) (memo (symbol-function fn-name))))

(defmacro defun-memo (fn args &body body)
    `(memoize (defun ,fn ,args . ,body)))

(defparameter *items* `((2 3) (1 2) (3 4) (2 2)))
(defparameter *weight* 5)

(defun-memo rec (index weight)
    (cond ((equalp index (length *items*)) 0)
        ((< weight (car (nth index *items*))) (rec (1+ index) weight))
        (t (max (rec (1+ index) weight)
               (+ (cadr (nth index *items*))
                   (rec (1+ index) (- weight (car (nth index *items*)))))))))

(defun solve ()
    (let ((price (rec 0 *weight*)))
        (format nil "~A" price)))

高速化するためにとりあえずmemo化した.


common lisp だとスッキリかけていいですね!