ちょっと前にカードゲームのデッキを作るためのスクリプトを作りました。 そのとき01ナップサック問題のアルゴリズムを使ったのですが、考え方についてちょっと引っかかったところがあり、理解するのに時間がかかってしまいました。 同じところで引っかかった人の役に立つかもしれないので、一応簡単にアルゴリズムの考え方をまとめておきます。
ナップザック問題の説明はwikipediaにお任せ。
- wikipedia.jp ... ナップサック問題
01ナップサック問題というのは、ナップサック問題の中でもそれぞれの物を持っていくか置いていくかの2択になっているものの事を言うようです。 それぞれの物を複数個選択できる場合は「個数制限なしナップサック問題」などと言うようです。
その他、参考にしたサイトはこちら。
- ITmedia ... 最強最速アルゴリズマー養成講座 : 病みつきになる「動的計画法」、その深淵に迫る
- en.wikipedia.org ... Knapsack problem
まずは適当な問題を考えましょう。
タカシ君は近日行われるチャリティーオークションに出品することにしました。 出品できそうな品物を探すと、それなりの重さがある物ばかりでした。 自分で運ぶことを考えると総重量は10kgくらいに抑えておいた方が良さそうです。 売値の期待値が最も大きくなる品物の組み合わせはどうなるでしょう?
出品できそうな品物の重さと期待できる売値は次の通りです。
| 品名 | 重さ | 売値 |
|---|---|---|
| カメラの三脚 | 3kg | 7千円 |
| 手提げ金庫 | 2kg | 4千円 |
| ゲーム機 | 2kg | 8千円 |
| 高圧洗浄機 | 5kg | 9千円 |
| 木彫りの置物 | 1kg | 3千円 |
| 電気ポット | 1kg | 5千円 |
重さの単位はkgで、問題の都合上整数です。 その他のツッコミどころとかはスルーでお願いします。
まずはとっかかりとなる考え方として、それぞれの品を持っていく/置いていくで場合分けをして総当りのグラフを書きましょう。 1つ目の品はカメラの三脚(3kg、7千円)です。
荷物が何もないところから始まって、三脚を持って行かない場合はそのまま、持っていく場合はその分の重さと価値を足します。
次の品物は手提げ金庫(2kg、4千円)です。
総当りということで、場合分けの数は倍々に増えていきます。
次の品物はゲーム機(2kg、8千円)です。
また前の品物の倍のノードが追加されました。 図でこれ以上描くのは面倒ですね。 面倒かどうかはさておき、2の品数乗のノードが必要になるというのは性能的に問題があります。 例題は6個なので26+25+24...程度のノードしか使いませんが、品数が100個の場合2100+...=1.26×1030+...ものノードが必要になります。 これではメモリにのりません。 たかだか100個程度の品数ですら計算できないという事になります。 話になりませんね?
というわけで、総当りという方針を捨てて計算の数を減らす工夫を考えましょう。 そこで注目するのは上の図の赤と青の太枠のノードです。 赤の方は総重量2kg、青の方は5kgのノードにつけた印となります。 赤い方に注目して、
- 左 : 現在の総重量2kg、売値期待値8千円
- 右 : 現在の総重量2kg、売値期待値4千円
このどちらかが解に到達するグラフのノードと仮定するなら、どちらを選べばいいのでしょう? 答えはもちろん、左の価値が高い方のノードですね。 現在の総重量が2kgなのであと8kg持てます。 残っている品物は3品です。 「荷物はあと8kg持っていけます。3品の中から荷物を選ぶとして、最も価値の高くなる組み合わせは?」という部分問題が残るわけですが、その解がどうであれ選別済みの2kgの荷物で価値が低い組み合わせを選ぶ理由はありません。 つまり、i個の荷物を選別した後w kgになるノードが複数ある場合、その中で選ぶべきノードは最も価値が大きいものだけで、それ以外のノードは無視してもかまわないのです。 これが計算の数を減らす工夫その1です。 これを採用して図を書き換えると、
色の薄い矢印は同じ重さのノードが重なった結果無視されるフローです。
もう1つ工夫しましょう。 それは当たり前で簡単なことです。 重量オーバーしたノードをそれ以降無視します。 この1つ1つ選別する考え方だと今選別中の品物を持っていくか置いていくかの選択はありますが、一度選択した品物を取り除くことはありません。 重量オーバーしたノードはそれ以降グラフを伸ばしても重量が減って有効になることは無いのです。
この工夫を採用して次の品物、高圧洗浄機(5kg、9千円)を追加した図を描くと、
右下の薄い矢印の先のアイコンは分銅のつもりです。 重量オーバーの印ということで。
ここで挙げた2つの工夫を実践するとノードの数はどうなるでしょう? まず、問題の都合で重さは整数値となっています。 重量の上限が決められているため取り得る値は0kg、1kg、2kg、...、10kgの11通りしかない事になります。 ある品物を選別したとき、同じ重さになったら一番価値の高いノード以外は無視、重量オーバーも無視となるので、用意するメモリの量は1つの品物につき(総重量の最大値+1)で済むことになります。 品数が100個の場合でも1.26×1030...個ものノード用にメモリを確保する必要はなくなります。
それをふまえてグラフを完成させると...矢印が少々入り乱れてしまいました。 横長にならないように詰めて書いたせいです。 やっぱり分かり易く書くにはある程度のスペースは必要ですね。 スペースがあるなら、置いていく場合/持っていく場合全部のノードを書いて無視するノードは×印で消すとかの方がよいのでしょう。 まぁ、考え方の根っ子については今までに書いてあるので、このグラフは流し読みでいいです。
最後の段のノードで最も売値の期待値が大きいのが解を得るために必要なノードです。 重さ9kg、売値の期待値2万7千円の図中で太枠になっているのがソレ。 問題で聞かれているのは品物の組み合わせです。 このノードから矢印を逆にたどることでそれぞれの品物を持っていく/置いていくべきかを調べましょう。 上の図では黒線の矢印が対象。
矢印をたどっていき、そこに書いてある○持っていく / ×置いていくの記号をメモしていくとこうなりました。
| 品名 | 重さ | 売値 | 持／置 |
|---|---|---|---|
| 電気ポット | 1kg | 5千円 | ○ |
| 木彫りの置物 | 1kg | 3千円 | ○ |
| 高圧洗浄機 | 5kg | 9千円 | × |
| ゲーム機 | 2kg | 8千円 | ○ |
| 手提げ金庫 | 2kg | 4千円 | ○ |
| カメラの三脚 | 3kg | 7千円 | ○ |
今回の解は1組でしたが、問題によっては解の組み合わせが複数の場合もあります。 その場合は解の経路上にあるノードのいくつかは有効な矢印2つから指されています。 必要ならば、両方の矢印をたどって全部の組み合わせをピックアップしましょう。
グラフを使った考え方は以上です。 次に、これをプログラムで書く場合について考えましょう。
ノードを減らすための2つの工夫のため、品物1つにつき必要なノードは(重量の上限+1)となっていました。 グラフを見ると初期状態(手ぶら)の段+品物の数だけ段があります。 問題を解くためのデータは(品物の数+1)行(重量の上限+1)列の配列で表すことができそうです。
2次元配列の1つ1つのには重量の合計と売値の期待値の合計の2要素が必要...ではありません。 2次元配列の各列で「重量の合計がwのときw番目の要素を使う」というルールにしておけばあらためて重量の合計を格納するためにメモリを確保する必要はないのです。 問題を解くためのデータは(品物の数+1)行(重量の上限+1)列の数字型の配列でokです。
では、実際に順を追って配列にデータを収めていく様子を確認していきましょう。 ネット上には最適化されたコードがいくつも落ちてますが、ここではそういうやり方ではなく、グラフをそのまま再現するようなやり方で書きます。 配列の変数は適当にdp[i,w]とでもしましょうか。 iは品物の番号、wはその時点での重量の合計を表すことにします。
まずは配列の初期化です。 各要素を「未使用」を表すデータで埋めます。 これはnullでもundefinedでもいいんですが、C言語風の書き方で「未使用の場合は-1」としましょう。 そして最初の何も持っていない状態(手ぶらで重さ0、売値の期待値0)を dp[0,0] = 0 というふうにセットします。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初期状態 | 0 | 0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| カメラの三脚(3kg、7千円) | 1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| 手提げ金庫(2kg、4千円) | 2 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| ゲーム機(2kg、8千円) | 3 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| 高圧洗浄機(5kg、9千円) | 4 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| 木彫りの置物(1kg、3千円) | 5 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| 電気ポット(1kg、5千円) | 6 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
1つ目の品物、カメラの三脚(3kg、7千円)を置いていく場合/持っていく場合のノードは次のように表現します。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初期状態 | 0 | 0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| カメラの三脚(3kg、7千円) | 1 | 0 | -1 | -1 | 7 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
プログラムの順番としては、まずdp[0,w]の行を w=0 から w=10 までチェックして-1以外の有効な数字が入っている要素を探します。 見つかった順にグラフでいうところの「置いてく矢印」と「持ってく矢印」の先にあたる要素の値を更新します。 初期状態なので、当然見つかるのはdp[0,0]のみです。 それを元に、次の行の三脚を置いていく場合/持っていく場合の値を反映させます。
品物を置いていく場合、重量の合計wは変わりません。 品物を置いていく場合のデータを入れる場所は同じwで1行下になります。 売値の期待値もそのまま変わらず、基準となるdp[0,0]の値をそのままコピーしましょう。
品物を持っていく場合、重量の合計wは三脚の重さだけ増えて 0+3 = 3 になります。 1行下のdp[1,3]にデータを入れましょう。 三脚の売値の期待値は7千円なので、入れる値は基準のdp[0,0]の値に7(千円)を足して7となります。 (表では千円の記述は省略)
同じように2つ目の品物、手提げ金庫(2kg、4千円)の処理をした後はこうなります。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初期状態 | 0 | 0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| カメラの三脚(3kg、7千円) | 1 | 0 | -1 | -1 | 7 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| 手提げ金庫(2kg、4千円) | 2 | 0 | -1 | 4 | 7 | -1 | 11 | -1 | -1 | -1 | -1 | -1 |
最初の行と同様にdp[1,w]の行を w=0 から w=10 までチェックして-1以外の有効な数字が入っている要素を探します。 それを元に次の行の要素を更新。 要素を入れる場所は、置いていく場合は基準となる要素の真下、持っていく場合は品物の重さだけ右にズレた要素の下です。
下の表は3つ目の品物、ゲーム機(2kg、8千円)の処理を途中までしたときの様子です。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初期状態 | 0 | 0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| カメラの三脚(3kg、7千円) | 1 | 0 | -1 | -1 | 7 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| 手提げ金庫(2kg、4千円) | 2 | 0 | -1 | 4 | 7 | -1 | 11 | -1 | -1 | -1 | -1 | -1 |
| ゲーム機(2kg、8千円) | 3 | 0 | -1 | 8 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
dp[2,2]を基準に処理する前の状態です。 置いていく場合は基準となる要素の真下を更新でしたね。 しかし、この要素はdp[2,0]を元にした更新ですでに値が埋まっています。 これは計算の数を減らす工夫その1「i個の荷物を選別した後w kgになるノードが複数ある場合、その中で選ぶべきノードは最も価値が大きいものだけ」のケースにあたります。 元からある値(この場合は8)とこれから更新しようとしている値(dp[2,2] = 4)を比べて大きい方の値を残します。 つまり、今回は値の上書きをしません。
持っていく場合は品物の重さだけ右にズレた要素の下を更新します。 行によって扱う品物は決まっているので、同じ行の持っていく場合の桁のズレ幅は一定になります。 基準の行を左から処理するというのと併せて考えると、更新先に値が入っていることはありません。 つまり、持っていく場合の処理は値の大きさを比べる必要はありません。 その代わり重量オーバーの可能性があるのでオーバーフローのチェックは必要になります。
それをふまえてdp[2,2]を基準に処理をするとこうなります。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初期状態 | 0 | 0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| カメラの三脚(3kg、7千円) | 1 | 0 | -1 | -1 | 7 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| 手提げ金庫(2kg、4千円) | 2 | 0 | -1 | 4 | 7 | -1 | 11 | -1 | -1 | -1 | -1 | -1 |
| ゲーム機(2kg、8千円) | 3 | 0 | -1 | 8 | -1 | 12 | -1 | -1 | -1 | -1 | -1 | -1 |
| 上書きしない↑ | ↑dp[2,2]+8で更新 | |||||||||||
こんな感じに処理を続けて、表を全部埋めてしまいましょう。 グラフで考えた場合と同じ意味を持つ配列はこうなります。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初期状態 | 0 | 0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| カメラの三脚(3kg、7千円) | 1 | 0 | -1 | -1 | 7 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| 手提げ金庫(2kg、4千円) | 2 | 0 | -1 | 4 | 7 | -1 | 11 | -1 | -1 | -1 | -1 | -1 |
| ゲーム機(2kg、8千円) | 3 | 0 | -1 | 8 | 7 | 12 | 15 | -1 | 19 | -1 | -1 | -1 |
| 高圧洗浄機(5kg、9千円) | 4 | 0 | -1 | 8 | 7 | 12 | 15 | -1 | 19 | 16 | 21 | 24 |
| 木彫りの置物(1kg、3千円) | 5 | 0 | 3 | 8 | 11 | 12 | 15 | 18 | 19 | 22 | 21 | 24 |
| 電気ポット(1kg、5千円) | 6 | 0 | 5 | 8 | 13 | 16 | 17 | 20 | 23 | 24 | 27 | 26 |
グラフで考えた場合と同様に、最後の行で最も値が大きいのが解を得るために必要な要素です。 重さ9kg、売値の期待値2万7千円の表中で太枠、背景色黄色になっているのがソレ。
グラフ相当の配列ができたので、次は持っていく品物の組み合わせをチェックしましょう。 グラフの場合は矢印を逆にたどってそれぞれの品物を持っていく/置いていくべきか振り分けました。 配列の数字から同じ事をするにはどうすればいいでしょうか?
まずは品物を置いていく場合について、重量の合計wが変わらないので基準要素の真下を更新するんでしたね。 その関係が成り立っているかどうかで「品物を置いていく場合だったのか?」を判定します。 更新処理のときに基準となった要素をdp[i,w]とした場合dp[i+1,w]に入っている値は、
- dp[i,w] != dp[i+1,w] の場合、別の基準要素を元にした「品物を持っていく場合」の値が入っている。
- dp[i,w] == dp[i+1,w] の場合、dp[i,w]を基準にした「品物を置いていく場合」の値で更新されている。 ... (1)
下の式の方を満たしているなら、その行の品物は置いていきます。 今回の例を見てみると、
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 木彫りの置物(1kg、3千円) | 5 | 0 | 3 | 8 | 11 | 12 | 15 | 18 | 19 | 22 | 21 | 24 |
| 電気ポット(1kg、5千円) | 6 | 0 | 5 | 8 | 13 | 16 | 17 | 20 | 23 | 24 | 27 | 26 |
dp[5,9]=21、dp[6,9]=27 なので条件を満たしません。 電気ポットは「持っていく」と分かります。
品物を持っていく場合のチェックもして本当に持っていくべきか確認してみましょう。 持っていく場合の更新処理は、「重量の合計wに品物の重さを足した要素の真下を更新」でした。 基準要素をdp[i,w]とした場合の更新の式は
- dp[i+1,w+品物の重さ] == dp[i,w]+売値の期待値
この関係がまだ保たれているならその行の品物は持っていきます。
この式は基準要素から見た形ですよね。 持っていく品物の組み合わせを確かめるときは下からたどっていくのでちょっと変形しましょう。
- dp[i+1,w'] == dp[i,w'-品物の重さ]+売値の期待値 (注 : 0 <= w'-品物の重さ) ... (2)
w'は組み合わせを調べるために着目した要素の重さです。 この例の場合は重さ9kg、売値の期待値2万7千円の要素がソレにあたるので、最初のw'は9です。 電気ポットの重さが1kgなので dp[6,9] と比べるのは dp[5,9-1] ですね。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 木彫りの置物(1kg、3千円) | 5 | 0 | 3 | 8 | 11 | 12 | 15 | 18 | 19 | 22 | 21 | 24 |
| 電気ポット(1kg、5千円) | 6 | 0 | 5 | 8 | 13 | 16 | 17 | 20 | 23 | 24 | 27 | 26 |
条件 dp[6,9] == dp[5,8]+5 を満たすので持っていく品だと確認できました。 以降、 dp[5,8] に注目して同じようにたどっていけば全ての品物について持っていく/置いていくが確認できます。
場合によっては持っていく/置いていく両方の条件を満たしている場合もあります。 「全ての組み合わせを答えなさい」というような問題だった場合は両方の経路をたどる必要があります。 でもまぁ、それを考えるのは今回のネタの本筋ではないので割愛しましょう。 例題の場合は1組しか解がないので考える必要もないですしね。
ここまでをふまえて、実際に経路をたどってみるとこうなります。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初期状態 | 0 | 0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | |
| カメラの三脚(3kg、7千円) | 1 | 0 | -1 | -1 | 7 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | 左上の要素との関係を満たすので ○ |
| 手提げ金庫(2kg、4千円) | 2 | 0 | -1 | 4 | 7 | -1 | 11 | -1 | -1 | -1 | -1 | -1 | 左上 ○ |
| ゲーム機(2kg、8千円) | 3 | 0 | -1 | 8 | 7 | 12 | 15 | -1 | 19 | -1 | -1 | -1 | 左上 ○ |
| 高圧洗浄機(5kg、9千円) | 4 | 0 | -1 | 8 | 7 | 12 | 15 | -1 | 19 | 16 | 21 | 24 | 真上 × |
| 木彫りの置物(1kg、3千円) | 5 | 0 | 3 | 8 | 11 | 12 | 15 | 18 | 19 | 22 | 21 | 24 | 左上 ○ |
| 電気ポット(1kg、5千円) | 6 | 0 | 5 | 8 | 13 | 16 | 17 | 20 | 23 | 24 | 27 | 26 | 左上 ○ |
無事に持っていく品物の組み合わせを求めることができました。
-
Note:
持っていく品物の組み合わせの調べ方について、最後に加えた品物を記憶する配列を別に用意して調べる方法もあるようです。 解の組み合わせが複数あっても1つしか求める必要がない場合はそちらの手法も検討しましょう。 その場合、テーブルdpはdp[i,?]とdp[i-1,?]の2行だけで済ませることができます。
- 参考 ... 津田塾大学 情報科学科の資料?
ここまでが考え方の基本です。 で、ネット上の同じような考え方で作られたハズのコードを見ると少々違うんですよね。 参考にしたのはen.wikipedia.orgのKnapsack problemのコードです。 4.1.2 0/1 Knapsack Problemのところに載っています。 (日本のwikipediaにはナップサック問題の簡単な説明しか載ってませんでした。ちょっと残念。)
参考コードとこのページで書いた考え方の基本とはちょっと違うように見えますが、やはり参考コードは基本を改良したものでした。 基本をどう変化させたら参考コードになるのか考えてみましょう。
参考コードは変数wが二重に宣言されていたり大文字のWと小文字のwが見分けづらかったりしたのでjavaで書き直してみました。 配列dpを計算する部分のコードです。
色々と気になるところがあります。 そして、wikipediaの本文には"The solution can then be found by calculating m[n,W]."という文が。 記号は違いますが、要は配列の右下が解を得るために必要な価値が最大となる要素だと言っています。 このページの例題だと右下ではなく、その左隣の価値が最大になりました。 どういう工夫をすれば必ず右下を最大にできるのでしょう?
まず、例題の場合について考えてみましょう。 この場合は、配列全体が1つ右にズレれば配列の右下要素の価値が最大となります。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初期状態 | 0 | -1 | 0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| カメラの三脚(3kg、7千円) | 1 | -1 | 0 | -1 | -1 | 7 | -1 | -1 | -1 | -1 | -1 | -1 |
| 手提げ金庫(2kg、4千円) | 2 | -1 | 0 | -1 | 4 | 7 | -1 | 11 | -1 | -1 | -1 | -1 |
| ゲーム機(2kg、8千円) | 3 | -1 | 0 | -1 | 8 | 7 | 12 | 15 | -1 | 19 | -1 | -1 |
| 高圧洗浄機(5kg、9千円) | 4 | -1 | 0 | -1 | 8 | 7 | 12 | 15 | -1 | 19 | 16 | 21 |
| 木彫りの置物(1kg、3千円) | 5 | -1 | 0 | 3 | 8 | 11 | 12 | 15 | 18 | 19 | 22 | 21 |
| 電気ポット(1kg、5千円) | 6 | -1 | 0 | 5 | 8 | 13 | 16 | 17 | 20 | 23 | 24 | 27 |
初期データのdp[0,1]に0を入れて処理を始めればこうなりますね。 初期データのdp[0,0]に0を入れるのは手ぶらを表していました。 1つ右にずらしてdp[0,1]に0を入れるのを例題の問題文にこじつけて考えるとどうなるでしょう? 「あらかじめ荷物にガラクタ(重さ1kg、売値の期待値0円)を持っていくことは決定している」とでも言えばいいんでしょうか?
これらの手ぶらの場合とガラクタ(重さ1kg、売値の期待値0円)を持っている場合は1つの配列にまとめていいんでしょうか? これはメモリの使用量を減らすために使った工夫1を流用すれば可能です。 実際にまとめる様子を、例を挙げて考えてみましょう。
工夫1を適用する条件は「現時点での総重量(残りの容量)、残りの品物が同じ」でした。 手ぶら(dp[0,0]=0)から手提げ金庫まで選別した場合と、
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初期状態 | 0 | 0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| カメラの三脚(3kg、7千円) | 1 | 0 | -1 | -1 | 7 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| 手提げ金庫(2kg、4千円) | 2 | 0 | -1 | 4 | 7 | -1 | 11 | -1 | -1 | -1 | -1 | -1 |
ガラクタ(1kg、0円)を持って(dp[0,1]=0)手提げ金庫まで選別した場合を比べると、
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初期状態 | 0 | -1 | 0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| カメラの三脚(3kg、7千円) | 1 | -1 | 0 | -1 | -1 | 7 | -1 | -1 | -1 | -1 | -1 | -1 |
| 手提げ金庫(2kg、4千円) | 2 | -1 | 0 | -1 | 4 | 7 | -1 | 11 | -1 | -1 | -1 | -1 |
dp[2,3] がぶつかっています。 この2つのdp[2,3] は「現時点での総重量(残りの容量)、残りの品物が同じ」です。 なので工夫1でいい方だけを残すことができます。
ぶつかっていない要素は、当然片方の配列にしか値はありません。 配列を2つ用意するのは容量の無駄なので手ぶらの方の配列にガラクタ(1kg、0円)の数字をおさめてしまいましょう。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初期状態 | 0 | 0 | 0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| カメラの三脚(3kg、7千円) | 1 | 0 | 0 | -1 | 7 | 7 | -1 | -1 | -1 | -1 | -1 | -1 |
| 手提げ金庫(2kg、4千円) | 2 | 0 | 0 | 4 | 7 | 7 | 11 | 11 | -1 | -1 | -1 | -1 |
太枠に背景色黄色のとこがいいとこ取りをした要素、背景色グレーがガラクタを持っていく場合の数字をコピーした要素を表しています。 このまま処理を進めても、要素がぶつかったところは同様に「いいとこ取り」をすれば問題なさそうです。 このように、工夫1のルールを上手く使えば2つの配列をまとめることができました。
ずらす数について、今回は答えを見て「1つずらせばいい」ということが分かってからずらしました。 しかし、全ての問題で2回解くというのは意味がありません。 そんなことをするくらいなら最後の行から最大値を探す方が建設的です。 では、1回解くだけで最大値を探すには? 簡単ですね、初期データに「手ぶらな場合、ガラクタ(重さ1kg、売値の期待値0円)を持っている場合、ガラクタ(2kg、0円)を持っている場合、ガラクタ(3kg、0円)を持っている場合、...」の全部を用意すればいいのです。 そうすればどれか1つは最適解になり、右下の要素に到達します。 参考にしたコードのように右下だけをチェックすればよくなります。
このやり方を採用すると「未使用」を表すデータも要らなくなります。 まず、初期データの配列の1行目は全て有効な値(ゼロ)になります。 それぞれの要素から見た「持っていかない場合」の要素は真下です。 品物がどうであれ、必ずそれぞれの行の全部の要素は少なくとも「持っていかない場合」に該当して更新されます。 処理の途中で基準となる要素が未使用になることはないのです。 基本のやり方どおりだと「この要素は未使用か?」というチェックが必要になるのですが、参考コードのやり方だとそれは不要になります。
ちょっとした工夫でループ内のコードもちょっとだけシンプルになり、最後の行で最大値を探す必要もなくなるんですね。
あらためて参考コードを見て、疑問に思うところはあと1点。 要素の更新部分です。
式に出てくる配列要素は左辺がdp[i+1][w]、右辺がdp[i][w]とdp[i][w-item.w]です。 グラフから配列の更新手順を考えたときは、「基準となる要素」から「置いていく場合はこの要素を更新」「持っていく場合はこの要素を更新」というふうに考えました。 参考コードはそうではなく、「更新される側の要素」1つに注目して「置いていく場合の基準となるのはこの要素」「持っていく場合は基準となるこの要素を元に計算」というふうに価値を計算して大きい方をおさめているようです。 if文で重さをチェックしているのは「着目した要素の重さ(w)-品物の重さ(item.w)」がマイナスになったら「持っていく場合」の基準要素が存在しないからです。 その場合は「置いていく場合」の更新だけでいいですね。
矢印の数を見て分かるとおり、この疑問については計算量が減るということでは無さそうです。 (もしかしたら突き詰めたらこっちの方が速いとかあるかもしれませんが、そのへん未確認です。) ともあれ、これで参考コードに対しての疑問は全て解けました。
例題を解くためのサンプルコード全体を載せておきます。
実行結果はこちら。
0: 0 < 0> 0 0 0 0 0 0 0 0 0 1: 0 0 0 7 [ 7] 7 7 7 7 7 7 カメラの三脚 2: 0 0 4 7 7 11 [11] 11 11 11 11 手提げ金庫 3: 0 0 8 8 12 15 15 19 [19] 19 19 ゲーム機 4: 0 0 8 8 12 15 15 19 (19) 21 24 高圧洗浄機 5: 0 3 8 11 12 15 18 19 22 [22] 24 木彫りの置物 6: 0 5 8 13 16 17 20 23 24 27 [27] 電気ポット 電気ポットは ○ 持っていく。 木彫りの置物は ○ 持っていく。 高圧洗浄機は × 置いていく。 ゲーム機は ○ 持っていく。 手提げ金庫 は ○ 持っていく。 カメラの三脚は ○ 持っていく。
出力の前半はprintDpTableメソッドによるdpの中身の出力、後半はprintTakeOrNotメソッドによる解の出力です。
printDpTableメソッドの出力にある要素の数字を囲む括弧は組み合わせをたどるときの様子をあらわしています。 [角括弧]は左上の要素と「持っていく場合」の関係を満たしている場合に表示されます。 (丸括弧)は真上の要素と「置いていく場合」の関係を満たしている場合に表示されます。 この例では表示されていませんが、両方を満たす場合は{波括弧}が表示されます。 下からたどっていって0行目に着いたら、その要素には<山括弧>が付きます。 行列の様子を見たり、デバッグに使ったりするためのメソッドなので見易くはありません。 実際に何かのアプリケーションを作る場合は不要なコードです。 というわけで作りも適当...
printTakeOrNotメソッドの出力は見ての通りです。 手抜きのため、解に複数の組み合わせがあっても1通りしか表示しません。 解の経路をたどるときに「持っていく場合」と「置いていく場合」の両方を満たす場合、「持っていく場合」を選ぶようになっています。 興味がある人は複数の組み合わせを出力できるようなコードを作ってみてください。
これで01ナップサック問題を解くアルゴリズムの説明は終わりです。
この投稿の冒頭で「カードゲームのデッキを作るためのスクリプトに01ナップサック問題のアルゴリズムを使った」と書きました。 一応簡単にどう使ったかをメモ書き程度ですが簡単に書いておきます。
例題ではパラメータに使った数値は重さと売値の期待値でした。 カードゲームのデッキを作る場合、それと同等の役割をするパラメータは重さの代わりにコスト、売値の期待値の代わりに攻撃力(など)です。 そして、普通のナップサック問題とは違いコスト制限に加えカードの枚数にも制限があります。 その違いを考慮してデッキ作成用のコードを考えました。
例題を解くとき、dpテーブルは品物の番号iとその時点での総重量wを添字にしていました。
- 品番号 ... i
- 制限 ... 重さw
品数+1の行が必要で、1行につき重さ制限+1の要素が必要でした。 カードゲームの場合はさらにデッキに使えるカード枚数の制限があります。
- カード番号 ... i
- 制限 ... コストc、デッキに使えるカード枚数n
制限が増えた分、配列の次数を増やしました。 配列 dp[i,c,n] は所有カードの枚数+1の層と、1層につき(コスト制限+1)行(デッキに使えるカード枚数+1)列の3次元になります。 デッキに使えるカード枚数は10枚までの固定値です。 なお、ネタの対象にしたゲームでは所有カードの枚数とかコスト制限とかを増やすのがとても大変なのでメモリ不足の心配はありません。
例題は dp[i,w] の i=0 の行を初期値0で埋めてから配列の更新を始めました。 カードゲームの場合は dp[i,c,n] の i=0 の層全体を初期値0で埋めてから配列の更新を始めます。
例題の場合はある行iの全ての要素それぞれを基準にして、次のi+1行を更新しました。 カードゲームの場合もある層iの全ての要素それぞれを基準にして、次のi+1番目の層を更新します。
3次元になってもグラフでいうところの矢印が増えるという事はありません。 置いていく/持っていくの2本の矢印に当たる処理を考えればokです。
置いていく場合の更新処理は、コスト合計とデッキで使うカードの枚数は変化しません。 dp[i,c,n] を基準とした場合、 dp[i+1,c,n] が更新対象になります。
持っていく場合の更新処理は、カードのコストの分だけcを増やし、デッキで使うカードの枚数を+1にします。 dp[i,c,n] を基準とした場合、 dp[i+1,c+カードのコスト,n+1] が更新対象です。
例題との違いはこんなもんですね。 品物1つに対して1行だったのがカード1枚につき1層になるだけでだいたい同じです。
でお買い物
