ひとりで勝手にはじめた蟻本読書会 本当は難しい貪欲法 選択肢を多く残す 蟻本読書会の続きです。今回から動的計画法ゾーンに入ります。
01ナップサック問題とは？
ナップサック問題、価値 viと重量 wi をもつ n 種類の品物が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その価値の合計を最大化するにはどうすればいいかという問題です。ナップサック問題には同じ種類の品物を1つまでしか入れられないものと、同じ品物をいくつでも入れてよいものがあります。前者が01ナップサック問題といわれているものです。
さっそく例題をみてみましょう。
総重量が大きくない場合
問題の趣旨は「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 の最大値を取れば解を得られます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, W; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; W = vs[1]; } long[] dp = new long[W + 1]; for (int i = 0; i < W + 1; i++) dp[i] = -1; dp[0] = 0; for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int w2 = vs[0]; int v2 = vs[1]; long[] dp2 = new long[W + 1]; for (int i = 0; i < W + 1; i++) dp2[i] = -1; for (int w = 0; w < W + 1; w++) { if (dp[w] >= 0) { if(w + w2 <= W && dp2[w + w2] <= dp[w] + v2) // その品物を選択する場合 dp2[w + w2] = dp[w] + v2; if(dp2[w] <= dp[w]) // その品物を選択しない場合 dp2[w] = dp[w]; } } dp = dp2; } Console.WriteLine(dp.Max()); } } |
この問題だと dp の更新される部分は更新元よりも後ろにあります。なのでひとつの配列を使い回すこともできます。これだとメモリーが節約できて処理速度も上がります。この場合、前から後ろに更新されるので内側のループは逆順に回さなければなりません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int w2 = vs[0]; int v2 = vs[1]; for (int w = W; w >=0; w--) { if (dp[w] >= 0) { if(w + w2 <= W && dp[w + w2] <= dp[w] + v2) dp[w + w2] = dp[w] + v2; } } } |
総重量が大きい場合
上と同じ問題ですが、制約が違います。
制約
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 の値を確認します。最後から要素をみていって最初に見つかった無限大以外の値が格納されている要素のインデックスの値が求める総価値の最大値です。
以下のコードではひとつの配列を使い回す方法を採用しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, W; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; W = vs[1]; } int vMax = (int)Math.Pow(10, 5); // 問題の制約より総価値はこれを超えない long[] dp = new long[vMax + 1]; for (int i = 0; i < vMax + 1; i++) dp[i] = long.MaxValue; dp[0] = 0; for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int w2 = vs[0]; int v2 = vs[1]; for (int v = vMax; v >=0; v--) { if (dp[v] < long.MaxValue) { if(dp[v] + w2 <= W && dp[v + v2] > dp[v] + w2) dp[v + v2] = dp[v] + w2; } } } for (int i = vMax; i >= 0; i--) { if (dp[i] < long.MaxValue) { Console.WriteLine(i); return; } } } } |
重さ以外の制約がついたナップサック問題
ナップサック問題では総重量を指定された値以下にするという制約要素がありましたが、それ以外にも選ぶ個数を指定された値以下にするなどの複数の制約がつく問題があります。この場合は dp を多次元配列にすることで対応します。
この問題は選んだスクリーンショットの幅の総和を 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 は以下のように更新されます。
|
1 2 3 4 5 6 7 |
// 選ばない場合 if(dp2[k, w] < dp1[k, w]) dp2[k, w] = dp1[k, w]; // 選ぶ場合（個数が K を超える場合や幅の総和が W を超える場合は不可） if (k + 1 <= K && w + A[i] <= W && dp2[k + 1, w + A[i]] < dp1[k, w] + B[i]) dp2[k + 1, w + A[i]] = dp1[k, w] + B[i]; |
更新処理が終わったらdpのなかから最大値を探します。それが問題の答えです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int W = int.Parse(Console.ReadLine()); int N, K; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; K = vs[1]; } int[] A = new int[N]; // 幅 int[] B = new int[N]; // 重要度 for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); A[i] = vs[0]; B[i] = vs[1]; } //dp[k][w] k 組選んだとき、幅の総和が w の時の重要度の最大値 int[,] dp = new int[K + 1, W + 1]; for (int r = 0; r < K + 1; r++) { for (int c = 0; c < W + 1; c++) dp[r, c] = -1; } dp[0, 0] = 0; for (int i = 0; i < N; i++) { int[,] dp2 = new int[K + 1, W + 1]; for (int r = 0; r < K + 1; r++) { for (int c = 0; c < W + 1; c++) dp2[r, c] = -1; } for (int k = 0; k <= K; k++) { for (int w = 0; w <= W; w++) { if (dp[k, w] < 0) continue; // 選ばない場合 if(dp2[k, w] < dp[k, w]) dp2[k, w] = dp[k, w]; // 選ぶ場合（個数が K を超える場合や幅の総和が W を超える場合は不可） if (k + 1 <= K && w + A[i] <= W && dp2[k + 1, w + A[i]] < dp[k, w] + B[i]) dp2[k + 1, w + A[i]] = dp[k, w] + B[i]; } } dp = dp2; } int ans = 0; for (int r = 0; r < K + 1; r++) { for (int c = 0; c < W + 1; c++) { if(ans < dp[r, c]) ans = dp[r, c]; } } Console.WriteLine(ans); } } |
部分和問題
部分和問題とは、与えられた値のなかからいくつかを選んで和を指定された値にできるかどうかを判定をする問題です。
与えられた 整数の配列 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
これも更新するときにループを逆に回せば同じ配列を使い回すことができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] P = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int max = 100 * N; bool[] dp = new bool[100 * N + 1]; dp[0] = true; foreach (int p in P) { for (int x = max; x >= 0; x--) { if(dp[x]) dp[x + p] = true; } } Console.WriteLine(dp.Count(_ => _ == true)); } } |
01ナップサック問題に類似した問題
重さとか価値は出てきませんが、01ナップサック問題に類似した問題を紹介します。
「気温によって着ることができる服が変化する。服の派手さの差の絶対値の総和の最大値を求めよ」という問題です。
これも選択可能な服を選択するかどうかで、dp にこれまで選択してきた服の派手さの差の絶対値の総和の最大値を記録していくことで解を得ることができます。
dp[v] を 前の日に着た服の派手さが v だったときの派手さの差の絶対値の合計と定義します。
dp は以下のように更新されます。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
v：前の日に着た服の派手さ wear.Value：その日に選ぶ服の派手さ // 選択するとき if(dp2[wear.Value] < dp1[v] + Math.Abs(v - wear.Value)) dp2[wear.Value] = dp1[v] + Math.Abs(v - wear.Value); // 選択しないとき if(dp2[v] < dp1[v]) dp2[v] = dp1[v]; 更新時に dp1 の Clone から dp2 を生成すれば選ばないときの処理を省略できる。 |
服は使用できる最低気温と最大気温、派手さの要素があるため Wearクラスを定義し、気温によって選択できる服を取得するGetWearsメソッドを定義しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
using System; using System.Collections.Generic; using System.Linq; class Program { class Wear { public Wear(int min, int max, int v) { Min = min; Max = max; Value = v; } public bool CanWear(int t) { if (t < Min || t > Max) return false; else return true; } public int Min = 0; public int Max = 0; public int Value = 0; } static void Main() { int D, N; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); D = vs[0]; N = vs[1]; } List<int> T = new List<int>(); for (int i = 0; i < D; i++) T.Add(int.Parse(Console.ReadLine())); List<Wear> wears = new List<Wear>(); for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int min = vs[0]; int max = vs[1]; int v = vs[2]; wears.Add(new Wear(min, max, v)); } Wear[] GetWears(int t) => wears.Where(_ => _.CanWear(t)).ToArray(); // 前の日の服の派手さが v だったときの派手さの差の絶対値の合計 dp[v] long[] dp = new long[100 + 1]; for (int i = 0; i < dp.Length; i++) dp[i] = long.MinValue; // 初日に選べる服（「前日」が存在しないので 0 を代入しておく） Wear[] firsts = GetWears(T[0]); foreach (Wear wear in firsts) dp[wear.Value] = 0; for (int d = 1; d < D; d++) { int t = T[d]; Wear[] ws = GetWears(t); long[] dp2 = (long[])dp.Clone(); for (int v = 0; v <= 100; v++) { if (dp[v] == long.MinValue) continue; foreach (Wear wear in ws) { if (dp2[wear.Value] < dp[v] + Math.Abs(v - wear.Value)) dp2[wear.Value] = dp[v] + Math.Abs(v - wear.Value); // dp.Clone() しているので選択しない場合の以下の処理は不要 //if(dp2[v] < dp[v]) // dp2[v] = dp[v]; } } dp = dp2; } Console.WriteLine(dp.Max()); } } |
「サイコロを 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 の値を足し合わせていきます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
i回目のサイコロの目が 1 なら dp[i + 1, c2, c3, c5] += dp[i, c2, c3, c5] / 6; 2 なら dp[i + 1, Min(c2 + 1, count2), c3, c5] += dp[i, c2, c3, c5] / 6; 3 なら dp[i + 1, c2, Min(c3 + 1, count3), c5] += dp[i, c2, c3, c5] / 6; 4 なら dp[i + 1, Min(c2 + 2, count2), c3, c5] += dp[i, c2, c3, c5] / 6; 5 なら dp[i + 1, c2, c3, Min(c5 + 1, count5)] += dp[i, c2, c3, c5] / 6; 6 なら dp[i + 1, Min(c2 + 1, count2), Min(c3 + 1, count3), c5] += dp[i, c2, c3, c5] / 6; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N; long D; { string[] vs = Console.ReadLine().Split(); N = int.Parse(vs[0]); D = long.Parse(vs[1]); } // D を素因数分解する int count2 = 0; int count3 = 0; int count5 = 0; while (D % 2 == 0) { D /= 2; count2++; } while (D % 3 == 0) { D /= 3; count3++; } while (D % 5 == 0) { D /= 5; count5++; } if (D != 1) { Console.WriteLine(0); return; } // dp[i][c2][c3][c5] := サイコロを i 回振って、2^c2 * 3^c3 * 5^c5 になる確率 double[,,,] dp = new double[N + 1, count2 + 1, count3 + 1, count5 + 1]; dp[0, 0, 0, 0] = 1; int[] d2 = { 0, 1, 0, 2, 0, 1 }; int[] d3 = { 0, 0, 1, 0, 0, 1 }; int[] d5 = { 0, 0, 0, 0, 1, 0 }; for (int i = 0; i < N; i++) { for (int c2 = 0; c2 <= count2; c2++) { for (int c3 = 0; c3 <= count3; c3++) { for (int c5 = 0; c5 <= count5; c5++) { for (int m = 0; m < 6; m++) { int res2 = c2 + d2[m]; if (res2 > count2) res2 = count2; int res3 = c3 + d3[m]; if (res3 > count3) res3 = count3; int res5 = c5 + d5[m]; if (res5 > count5) res5 = count5; dp[i + 1, res2, res3, res5] += dp[i, c2, c3, c5] / 6; } } } } } Console.WriteLine(dp[N, count2, count3, count5]); } } |
