D - ナップサック問題の解説（その2）

何の話かというと

enakai00.hatenablog.com

上記のエントリーの続きです。はい。

「DPの考え方」に立ち戻る

前回紹介したナップサック問題の解法は、伝統的に言い伝えられて来たものですが、ぶっちゃけ、w0 = 0,...,W のすべて条件を個別に考えるって、気持ちわるいですよね・・・。まさに「お前よく思いついたよなぁ。。。。」的な解法です。ただ、前回の最後に触れたように、W が巨大になるとこのやり方は破綻してしまいます。もっと効率的に解けないものでしょうか。

まず、「DPの考え方」に立ち戻ると、まずは、「n-1 個目までのデータで解いた場合の何らかの情報 dp[n-1]」があって、この情報に、n 個目のデータの情報をプラスすることで、新たに「n個目までのデータで解いた場合の何らかの情報 dp[n]」を計算するということが基本になります。そこで「とんち問題」的な発想はいったん脇において、愚直な数え上げについて、もう一度考えてみましょう。「E -Mod i の解説」でも触れたように、「しらみつぶし」パターンを考えるのは、頭を整理するという意味では、決して無駄ではありません。

今回のケースでは、それぞれの荷物について、「入れる」「入れない」の二択の判断が入ることになります。実際にナップサックに入り切るかどうかは別にして、

・1個目の荷物を入れない場合
・1個目の荷物を入れる場合

の結果を記録して、その結果に基づいて、

・2個目の荷物を入れない場合
・2個目の荷物を入れる場合

の結果を記録して、その結果に基づいて、

・3個目の荷物を入れない場合
・3個目の荷物を入れる場合

・・・ということを N 個目の荷物まで繰り返せば、あらゆる組み合わせパターンを記録することができます。まともに考えると、 $2^N$ 種類のケースが登場するので、ものすごく非効率なアルゴリズムになりそうですが、今はそこは気にせずに、まずは、計算記録の帳簿 dp[n] にどのような情報を残せばよいかをじっくりと考えてみましょう。

ちなみに、前回の教科書解法では、

・・・・通常の思考では、こうなるのですが、ここで、ちょっとだけ発想を逆転します。今はとにかく、2個目の荷物を入れるという大前提で考えているわけですので、まず、からっぽのナップサックを用意して、先に2個目の荷物を入れてしまいます。

という、これまた「とんち問題」的な発想がありましたが、今回は、こういった「とんち」はやめて、愚直に1個目の荷物から順番に入れていきます。

まずは、

・1個目の荷物を入れない場合
・1個目の荷物を入れる場合

の結果を記録するわけですが、この後の処理で必要な情報はいったい何でしょうか・・・？　次に2個目の荷物を入れるかどうかを考える際に、残り容量が足りるかどうかが重要ですよね。それぞれのケースでの残り容量（W、および、W-w[1]）は記録することにします。そしてもちろん、それぞれの場合に実現できる価値（0、および、v[1]）も必要です。ただし、残り容量はさまざまな値をとるので、仮に、「残り容量」を添字とするリストに記録するとなると、前回と同様に巨大なリストが必要になって破綻します。そこで、今回は、「残り容量」をキーとするディクショナリーを利用することにします。コードにするとこんな感じでしょうか。

[code01]

dp = [{} for _ in range(N+1)] # dp[1], dp[2], ... には、それぞれにディクショナリーが入っている

dp[1][W] = 0         # 1個目を入れない場合
if w[1] <= W:
  dp[1][W-w[1]] = v[1] # 1個目を入れる場合

dp[1] に保存されたディクショナリーは、「残り容量」と「価値」の Key-Value ペアを格納しており、「（1個目の荷物だけを使った場合に）その残り容量で実現できた価値」を記録していることが分かります。（1個目を入れる場合を考える際は、ナップサックの残容量と1個目の荷物の重さを比較して、ちゃんと入れられる場合だけを考える様にしています。）

では、これを踏まえて、2個目の荷物を考えましょう。こちらについても、

・2個目の荷物を入れない場合
・2個目の荷物を入れる場合

の2通りの結果があります。

なんとなくの流れできまっちゃいましたが、dp[2] は「（2個目までの荷物を使った場合に）その残り容量で実現できた価値」を記録するわけですので、2個目の荷物を入れない場合、その結果は、dp[1] としてすでに記録されています。思い切って、コピーしちゃいましょう。（Python のディクショナリー要素はミュータブルなので、代入ではなくて、明示的にコピーする点に注意してください。）

dp[2] = copy.copy(dp[1]) # 2個目を入れない場合

この時点で、dp[2] には、「（1を入れない, 2を入れない）（1を入れる, 2を入れない）」の2種類の場合の情報が記録されています。

さらに、2個目の荷物を入れる場合の情報を加えましょう。正確には、「（1を入れない, 2を入れる）（1を入れる, 2を入れる）」の2種類を追加する必要がありますが、dp[1] の中から、1個目を入れない場合と入れる場合の個別の情報はどうやって取り出せばよいのでしょうか？　これは、ディクショナリー dp[1] のキーの値（具体的には、[code01] で使用した W、および、W-w[1]）から、間接的に取り出すことができます。キーの値 w0 は、（1個目を処理した結果の残容量）なので、w[2] <= w0 であれば2個目を入れる場合を考えることができて、入れた場合の新たな残容量は、w0-w[2]、新たな合計価値は、dp[1][w0] + v[2] と決まります。次のように、キーを取り出しながらループを回せば、1個目を入れない場合と入れる場合を網羅できるでしょう。

for w0 in dp[1].keys():
  if w[2] <= w0: # 2個目を入れる場合
    dp[2][w0-w[2]] = dp[1][w0] + v[2]

ただし！　ここで重要な注意点があります。（最初、これを見落としていて、正しいコードにたどりつくのに一晩かかっちゃいました。。。）

dp[2] には、先ほどコピーした dp[1] の情報がすでに入っていますので、もしかしたら、2個目を入れる場合のキーの値 w0-w[2] について、すでに何らかの情報を格納している可能性があります。たとえば、1個目の荷物を入れた際の残容量 W-w[1] がここでの w0-w[2] と同じ値だったらどうなるでしょうか？

・・・本当にそんなことあるの？？？

あります。

・・・どんな場合？？？

たとえば、1個目と2個目の荷物が同じ重さだとしましょう。dp[1][W-w[1]] には、「1個目の荷物を入れた場合」の価値 v[1] が記録されています。同じものが dp[2][W-w[1]] にもコピーされており、これは、(1を入れる, 2入れない) ケースの価値にあたります。

一方、2個目の荷物を入れる場合のループを回すと、w0 = W（つまり、1個目の荷物を入れない場合）のキー w0-w[2] は W-w[1] と一致します。要するに、(1を入れる, 2を入れない) と (1を入れない, 2を入れる) は、残容量が一致してディクショナリーのキーが被るのです。

この場合、すでに記録されている (1を入れる, 2を入れない) ケースの価値 v[1] の情報を残すべきか、新たに発見された (1を入れない, 2を入れる) ケースの価値 dp[1][W] + v[2] = v[2] の情報で上書きするべきか、どちらが正解なのでしょう？？？

結論からいうと、値が大きい方を残すべきです。今、解こうとしている問題は、価値をどこまで上げられるか、という問題ですので、同じ残容量であれば、当然ながら、より高い価値を実現するケースの方が後々で必要になるはずです。というわけで、この点を考慮したコードは次の様になります。（先に説明した「2個目を入れない場合」もくっつけておきました。）

dp[2] = copy.copy(dp[1]) # 2個目を入れない場合

for w0 in dp[1].keys():
  if w[2] <= w0: # 2個目を入れる場合
    if w0-w[2] in dp[2].keys():
      dp[2][w0-w[2]] = max(dp[2][w0-w[2]], dp[1][w0] + v[2])
    else:
      dp[2][w0-w[2]] = dp[1][w0] + v[2]

これで繰り返しのパターン（dp[n-1] から dp[n] を求める遷移処理）が見えて来たのではないでしょうか。1 -> n-1、2 -> n の置き換えてオッケーですね。せっかくなので、n についての 2 ... N のループも回してしまいましょう。

for n in range(2, N+1):
  dp[n] = copy.copy(dp[n-1]) # n個目を入れない場合

  for w0 in dp[n-1].keys():
    if w[n] <= w0: # n個目を入れる場合
      if w0-w[n] in dp[n].keys():
        dp[n][w0-w[n]] = max(dp[n][w0-w[n]], dp[n-1][w0] + v[n])
      else:
        dp[n][w0-w[n]] = dp[n-1][w0] + v[n]

最終的に得られるディクショナリー dp[n] の中には、N 個の荷物の「入れる／入れない」の $2^N$ 通りのすべての組み合わせ（正確には、その中でナップサックに入る組み合わせ）について、それぞれに対するナップサックの残容量と合計価値が記録されています。組み合わせの中には、残容量がたまたま一致するものもありますが、それらについては、合計価値が大きい方の値がちゃんと記録されています。いや、よくできているじゃないですか。

最後に、dp[n] に記録された合計価値の最大値を答えれば、問題の回答になります。

「前から順番に考える」という発想で組み立てたので、あまりDPっぽくないかもしれませんが、dp[1],...,dp[n-1] と A[n]（今の場合は w[n] と v[n]）だけを使って dp[n] を求める（遷移処理を行う）という意味では、ちゃんとDPの立て付けになっている点を味わってみてください。

一般的なDPでは、適切な遷移処理を「思いつく」ために、後ろから前を振り返るという、逆転というか、とんち的な発想が必要になりますが、実際の処理としては、あくまで、前から順番にやるという愚直な計算方式なのです。

リストを使った実装との比較

さて・・・、リストの代わりにディクショナリーを利用して、「巨大なリスト問題」を解決したふりをしていますが・・・、本当に解決できたのでしょうか？

じつは！！！！

ここまででは、まだ問題は解決できていません。前述の説明を振り返りましょう。

最終的に得られるディクショナリー dp[n] の中には、N 個の荷物の「入れる／入れない」の $2^N$ 通りのすべての組み合わせ（正確には、その中でナップサックに入る組み合わせ）について、それぞれに対するナップサックの残容量と合計価値が記録されています。

そう、繰り返しを進めるごとにディクショナリーのキーの数は、（残容量の偶然の一致を除いて）倍々に増えていくので、最終的には、 $2^N$ 個ものキーを持った巨大なディクショナリーができあがってしまいます。N が大きくなると、dp[n-1] のキーについてのループが指数的に長くなり、実行時間が耐えられなくなります。もちろん、ディクショナリーを記憶するメモリー容量も足りなくなる可能性があります。

ただし、これは逆の見方をすると、リストを使った実装が問題を抱えている根本的な理由がわかったことにもなります。リスト実装の場合も、結局のところは、（直感的には分かりにくいのですが・・・） $2^N$ 通りのすべての組み合わせに対する情報を記録することになっており、そのために必要な記録場所として、はじめから巨大なリストdp[ ][ ]を用意していたというわけなのです。

ただ、今回のディクショナリー実装のよい所は、

・最初から巨大な記憶領域を確保しなくてよい
・数え上げ方式との対応が直感的にわかり、どこでメモリーを消費して、どこで計算が長くなるかが把握できる

という点にあります。この利点を活かして、メモリー消費や実行時間をできるだけ小さくする工夫を加えていくことにしましょう。

不要な記録の削除

ここまで、DPの遷移処理について、「dp[1],...,dp[n-1] と A[n]（今の場合は w[n] と v[n]）だけを使って dp[n] を求める」と説明してきましたが、今回のケースでは、dp[n] を求める際に必要なのは、dp[n-1] と w[n]、v[n] だけで、それより古い dp[1],...,dp[n-2] は必要ありません。したがって、dp[n] の計算が終わった段階で、dp[n-1] はメモリー上から破棄しても構いません。こんな感じの実装をとることができます。

  dp = {}
  dp[W] = 0               # 1個目を入れない場合
  if w[1] <= W:
    dp[W-w[1]] = v[1]     # 1個目を入れる場合

  for n in range(2, N+1):
    dp_n = copy.copy(dp)  # n個目を入れない場合
    for w0 in dp.keys():
      if w[n] <= w0:      # n個目を入れる場合
        if w0-w[n] in dp_n.keys():
          dp_n[w0-w[n]] = max(dp_n[w0-w[n]], dp[w0] + v[n])
        else:
          dp_n[w0-w[n]] = dp[w0] + v[n]
    dp = dp_n

  print(max(dp.values()))

dpがこれまでのdp[n-1]で、dp_nがこれまでのdp[n]に対応します。dp_nが計算できたら、これをdpとして次のループ処理へと進みます。dp_nの計算中はdpを参照するので、dp->dp_nはまじめにコピーしていますが、dp_n->dpは代入による論理コピーで大丈夫です。dpが巨大なディクショナリーになると、コピー時間も馬鹿にならないので、コピーの回数を減らす地味な努力をしています。

さあ、ここまでの成果を提出して結果を確認してみましょう。まだまだ制限時間オーバーの可能性が高いですが、簡単なサンプルケースに通るかどうかで、ロジックがまちがっていないかは確認できるはずです。

atcoder.jp

サブタスク3で制限時間オーバーしていますが、それ以外はパスしているようです。ちょっとだけ（かなり？）進歩しましたね。

ちなにみ、サブタスク3と言うのは、 $1\le N\le 200$ かつ $0\le v_1\le 1000$ という条件があるもので、重さが巨大になる可能性があります。