ひとりで勝手にはじめた蟻本読書会 本当は難しい貪欲法 選択肢を多く残す 蟻本読書会の続きです。今回から動的計画法ゾーンに入ります。

01ナップサック問題とは?

ナップサック問題、価値 viと重量 wi をもつ n 種類の品物が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その価値の合計を最大化するにはどうすればいいかという問題です。ナップサック問題には同じ種類の品物を1つまでしか入れられないものと、同じ品物をいくつでも入れてよいものがあります。前者が01ナップサック問題といわれているものです。

さっそく例題をみてみましょう。

総重量が大きくない場合

D – Knapsack 1

問題の趣旨は「N 個の品物がある。品物 i の重さは w[i] で、価値は v[i] である。重さの総和を W 以下で価値の総和を最大にしようとした場合、価値の総和の最大値を求めよ」です。

制約
1 ≦ N ≦ 100
1 ≦ W ≦ 10^5
1 ≦ w[i] ≦ W
1 ≦ v[i] ≦ 10^9

すべての品物について入れる入れないを考えるという全探索を行えば、その計算量は O(2^n)となります。N = 10 程度であれば問題ありませんが、少し大きな値になると制限時間内には終わりません。N = 100 なら絶対に無理です。そこで動的計画法で解きましょう。

要素数 W + 1 の配列 dp を定義します。そして dp[w] をこれまでに選んだ品物の重量の総和を w としたときの価値の総和の最大値と定義します。まず dp 全体を -1 で初期化して dp[0] = 0 を代入します。これは最初はなにも選んでいないので選ばれた品物の総重量は 0、価値の総和も 0 であることを意味しています。-1 はそのような選び方は発見されていないことを意味しています。

これから 品物 i を選ぶかどうかひとつひとつ見ていくのですが、このとき dp[w] の値は以下のように変化していきます(変化前を dp1、変化後を dp2 とする)。

品物 i を選ぶ場合は選ばれた品物の総重量がそれだけ重くなり、価値の総和もそれだけ大きくなります。この場合は dp1 と dp2 の関係は以下のようになります。

dp2[w + w[i]] = dp1[w] + v[i] (品物 i を選ぶ場合。w + w[i] ≦ W)
dp2[w] = dp1[w] (品物 i を選ばない場合)
ただし、dp2[w] に複数の値が入るときは最大のものを採用する

注意点として w + w[i] が W を超えると配列の範囲外にアクセスして例外が発生するということです。これは選ばれた品物の総重量が W を超えているので対象から外さなければなりません。

最後に dp の最大値を取れば解を得られます。

この問題だと dp の更新される部分は更新元よりも後ろにあります。なのでひとつの配列を使い回すこともできます。これだとメモリーが節約できて処理速度も上がります。この場合、前から後ろに更新されるので内側のループは逆順に回さなければなりません。

総重量が大きい場合

E – Knapsack 2

上と同じ問題ですが、制約が違います。

制約
1 ≦ N ≦ 100
1 ≦ W ≦ 10^9
1 ≦ w[i] ≦ W
1 ≦ v[i] ≦ 10^3

今度は配列 dp[W + 1] を宣言しようとすると大きすぎてメモリーが足りません。しかし v[i] は小さいです。v[i] の総和は 10^3 * N であり、10^5 以下です。そこで dp[v] には総価値を v にするための総重量の最小値を格納することにします。

dp[v] には総価値を v にするための総重量の最小値を格納することにするので、そのような選び方が発見されていないときは dp の各要素を無限大で初期化しておきます。そしてなにも選ばないときは総価値は 0、総重量も 0 であることだけはわかっているので dp[0] = 0 としておきます。

あとは以下のように更新していきます。

dp2[v + v[i]] = dp1[v] + w[i] (品物 i を選ぶ場合。ただし dp1[v] + w[i] ≦ W)
dp2[v] = dp1[v] (品物 i を選ばない場合)
ただし、dp2[v] に複数の値が入るときは最小のものを採用する

最後まで dp を更新していって dp の値を確認します。最後から要素をみていって最初に見つかった無限大以外の値が格納されている要素のインデックスの値が求める総価値の最大値です。

以下のコードではひとつの配列を使い回す方法を採用しています。

重さ以外の制約がついたナップサック問題

ナップサック問題では総重量を指定された値以下にするという制約要素がありましたが、それ以外にも選ぶ個数を指定された値以下にするなどの複数の制約がつく問題があります。この場合は dp を多次元配列にすることで対応します。

D – 高橋くんの苦悩

この問題は選んだスクリーンショットの幅の総和を W 以下にすることと選ぶスクリーンショットの個数を K 以下にするというふたつの制約が科せられています。そのうえで重要度の総和の最大値を求めよというのがこの問題の趣旨です。

制約
1 ≦ N ≦ 50
1 ≦ W ≦ 10000
1 ≦ K ≦ N

dp を以下のように定義します。

dp[k][w] k 組選んだとき、幅の総和が w の時の重要度の最大値

最初はどれも選んでいないので要素全体を -1 で初期化します。そしてどれも選ばなければ選んだ個数は 0 で幅の総和も 0 であり、重要度の総和も 0 なので dp[0, 0] = 0 としておきます。

dp は以下のように更新されます。

更新処理が終わったらdpのなかから最大値を探します。それが問題の答えです。

部分和問題

部分和問題とは、与えられた値のなかからいくつかを選んで和を指定された値にできるかどうかを判定をする問題です。

A – コンテスト

与えられた 整数の配列 P(1 ≦ P[i] ≦ 100)のなかからいくつかを選んだときその総和は何通り存在するかを問う問題です。

入力されるデータの制約から総和の最大値は 100 * N を超えることはありません。そこで dp = new bool[100 * N + 1] を宣言します。dp[p]には 総和が p になるかどうかを格納します。最初はなにも選ばないなら総和は 0 であることだけがわかっています。なので dp[0] = true とします。

あとは P[i] を取得して dp を更新していきます。


dp1[x] == true ならば dp2[x + P[i]] == true

これも更新するときにループを逆に回せば同じ配列を使い回すことができます。

01ナップサック問題に類似した問題

重さとか価値は出てきませんが、01ナップサック問題に類似した問題を紹介します。

D – 暑い日々 (Hot days)

「気温によって着ることができる服が変化する。服の派手さの差の絶対値の総和の最大値を求めよ」という問題です。

これも選択可能な服を選択するかどうかで、dp にこれまで選択してきた服の派手さの差の絶対値の総和の最大値を記録していくことで解を得ることができます。

dp[v] を 前の日に着た服の派手さが v だったときの派手さの差の絶対値の合計と定義します。

dp は以下のように更新されます。

服は使用できる最低気温と最大気温、派手さの要素があるため Wearクラスを定義し、気温によって選択できる服を取得するGetWearsメソッドを定義しています。

D – サイコロ

「サイコロを N 回振ったとき、出た目の積が D の倍数となる確率を求めよ」という問題です。

制約
1 ≦ N ≦ 100
1 ≦ D ≦ 10^18

サイコロの目を素因数分解すると、2, 3, 5しか現れないことに着目します。するとサイコロの目に存在する素因数 2, 3, 5 の指数のみを考えれば良いことに気づきます。

まず D を素因数分解し、素因数 2,3,5 の個数を変数 count2, count3, count5 に格納しておきます。このときに 2, 3, 5 以外の素因数がある場合はサイコロの出目の総積が D になることは絶対にないので 0 を出力します。

double型4次元配列 dp[i, c2, c3, c5] をサイコロを i 回振って、2^c2 * 3^c3 * 5^c5 になる確率と定義します。サイコロを振るたびに出目によって素因数 2, 3, 5 の数が増えていきます。これを更新していきます。それぞれの出目がでる確率は 1 / 6 なので dp[i, c2, c3, c5] の 1 / 6 の値を足し合わせていきます。