ナップサック問題の基本形には「n種類の品物が1個ずつ」という条件が付いていた。よって、この条件を無くした問題を考えよう、という話が自然に出てくる。
条件の有無を区別するため、前者を「0-1ナップサック問題」、後者を「個数制限なしナップサック問題」とか "UKP: unbounded knapsack problem" と呼ぶのが一般的らしい。
何も考えないで入力を与えると両者の違いが現れないこともあるが、たとえば (重さ, 価値) のリストが((2 2) (3 4) (5 7))、重さの制限W=9 と与えると次のように出力に違いが出てくる。
- 0-1ナップサック問題の場合
- 答え 11 … (3 4) と (5 7) の要素を選択するので 4 + 7 で 11
- 個数制限なしナップサック問題の場合
- 答え 12 … (3 4) の要素を3個選択するので 4 × 3 で 12
以下、個数制限なしのほうを解くプログラムを考える。と言っても 0-1ナップサック問題を再帰的に解いている場合は少し変更するだけで個数制限なしのほうも解ける。
;; 0-1ナップサック問題
(defun knapsack (lst w)
(cond
((null lst) 0)
(t (if (> (caar lst) w) ;先頭の品物が入らない場合
(knapsack (cdr lst) w)
(max ;入れる場合と入れない場合を両方とも試し、良い結果のほうを選ぶ
(+ (cadar lst) (knapsack (cdr lst) (- w (caar lst))))
(knapsack (cdr lst) w))))))
上のプログラムの後半部分（(max)の中）で、先頭の品物を何度も入れるようにする。具体的には、
(max ;入れる場合と入れない場合を両方とも試し、良い結果のほうを選ぶ
(+ (cadar lst) (knapsack (cdr lst) (- w (caar lst))))
(knapsack (cdr lst) w))))))
を次のように変える。
(max ;先頭の品物を繰り返し入れる場合と、入れない場合を試して良いほうを選ぶ
(+ (cadar lst) (knapsack lst (- w (caar lst))))
(knapsack (cdr lst) w))))))
要するに (cdr lst)をlstに変え、コメントを編集しただけ。
最後に確認。
(defun knapsack (lst w)
(cond
((null lst) 0)
(t (if (> (caar lst) w) ;先頭の品物が入らない場合
(knapsack (cdr lst) w)
(max ;先頭の品物を繰り返し入れる場合と、入れない場合を試して良いほうを選ぶ
(+ (cadar lst) (knapsack lst (- w (caar lst))))
(knapsack (cdr lst) w))))))
=> knapsack
(knapsack '((2 2) (3 4) (5 7)) 9)
=> 12
この関数の引数を眺めてみると、最大で n × W 種類しかないことが自然に分かる。つまり個数制限無しの場合も、0-1の場合と同じく n × W のメモ化テーブルに結果を保持することで計算量を減らせる。
0 件のコメント:
コメントを投稿