個数制限つき部分和問題 in Elisp

プログラミングコンテストチャレンジブック演習「個数制限付き部分和問題」 - 日々精進に問題文が載っている。これも動的計画法の問題。

とりあえず性能を考えずに書いてみた場合

再帰で自然に書ける。

;;; 個数制限つき部分和問題
;;; - 数と個数のリスト ((数 個数) (数 個数) (数 個数) ...) 
;;; - 総和 K
;;; を与える。総和Kを満たす組合せが存在する場合は t を、その他の場合は nil を返す。
(defun solve (lst K)
  (cond
   ((zerop K) t)                        ;ちょうどゼロ => t
   ((< K 0) nil)                        ;マイナス => 解なし
   ((null lst) nil)                     ;もう追加できない => 解なし
   (t (or
       (if (< 0 (cadar lst))            ;数を追加できる（0個以上ある）
           (solve (decrease-first-num lst) (- K (caar lst))))
       (solve (cdr lst) K)))))          ;次の数を試す
=> solve
;;; 補助関数
(defun decrease-first-num (lst)
  (cons (list (caar lst) (1- ( cadar lst))) (cdr lst)))
=> decrease-first-num
;;; 補助関数の動作確認
(decrease-first-num '((1 4) (2 2) (3 3)))
=> ((1 3) (2 2) (3 3))
;;; 動作確認
(solve '((3 3) (5 2) (8 2)) 17)
=> t
(solve '((3 3) (5 2) (8 2)) 15)
=> nil

性能改善版（動的計画法あるいはメモ化）による

まず、関数solveの引数が取り得る範囲を減らすため、数の「個数」の部分を1ずつ減らしたりせず固定する。すると第一引数のlstを最大n種類になるので、第二引数のKと合わせて最大 n * K の組み合わせで全ての引数が表現でき、メモ化などで計算量を抑えることができる。その代わり関数の戻り値を t, nil の2値ではなく整数にして、リストの先頭の数が何個余るかを表すようにする（Kになる組み合わせがないときは -1 で表す）。

とりあえず数が1種類の場合と空リストの場合だけ考えると、

(defun solve* (lst K)
  (cond
   ((null lst) -1)                      ;空リストなら解なし
   ((zerop K) (second (car lst)))       ;K=0なら数を1個も消費しないので、個数をそのまま返す
   ((< K (first (car lst))) -1)         ;数が大き過ぎるなら解なし
   ((and (<= (first (car lst)) K)       ;Kから数を引くことができる?
         (< 0 (solve* lst (- K (first (car lst)))))) ;Kから数を1個引いた場合の問題を解いたら、まだ数が余る?
    (1- (solve* lst (- K (first (car lst)))))) ;余った数から1を引くと、解になる
   (t -1)))                             ;その他の場合は解けない
=> solve*

;;; テスト
(solve* '() 2)
=> -1

(solve* '((2 1)) 1)
=> -1

(solve* '((2 1)) 2)
=> 0 ;解あり

(solve* '((2 1)) 3)
=> -1

この発想になれたら、数が何種類もある場合も考慮する。先頭の要素をスキップしても解けたという場合を追加するだけなのであまり変わらないが、次のようになる。

(defun solve* (lst K)
  (cond
   ((null lst) -1)                      ;空リストなら解なし
   ((or (zerop K)                       ;K=0?
        (<= 0 (solve* (cdr lst) K)))    ;現在の数をスキップして解いたら、解けた?
    (second (car lst)))                 ;現在の数を1個も消費しないので、個数をそのまま返す
   ((< K (first (car lst))) -1)         ;数が大き過ぎるなら解なし
   ((and (<= (first (car lst)) K)       ;Kから数を引くことができる?
         (< 0 (solve* lst (- K (first (car lst)))))) ;Kから数を1個引いた場合の問題を解いたら、まだ数が余る?
    (1- (solve* lst (- K (first (car lst)))))) ;余った数から1を引くと、解になる
   (t -1)))                             ;その他の場合は解けない
=> solve*

;;; テスト
(solve* '((2 2) (4 2) (6 2) (8 2)) 40)
=> 0 ;解あり

(solve* '((2 2) (4 2) (6 2) (8 2)) 39)
=> -1

あとは、例によってこの再帰的関数をメモ化するとよい。

参考

• プログラミングコンテストチャレンジブック演習「個数制限付き部分和問題」 - 日々精進
• Amazon.co.jp： プログラミングコンテストチャレンジブック: 秋葉 拓哉, 岩田 陽一, 北川 宜稔: 本