ひとりで勝手にはじめた蟻本読書会 本当は難しい貪欲法 選択肢を多く残す 蟻本読書会の続きです。今回から動的計画法ゾーンに入ります。
Contents
01ナップサック問題とは？
ナップサック問題、価値 viと重量 wi をもつ n 種類の品物が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その価値の合計を最大化するにはどうすればいいかという問題です。ナップサック問題には同じ種類の品物を1つまでしか入れられないものと、同じ品物をいくつでも入れてよいものがあります。前者が01ナップサック問題といわれているものです。
ズバリこんな問題です。この問題、1 ≦ W ≦ 10^9 という制約があって一筋縄ではいかないのですが、W が極端に大きな値でなければ比較的簡単にできます。
N 個の荷物があり、i(1 ≦ i ≦ N) 番目の荷物には価値 v_i と重さ w_i が割り当てられている。許容重量 W のナップサックが1つある。重さの和が W 以下となるように荷物の集合を選びナップサックに詰め込むとき、価値の和の最大値を求めよ。ただし、同じ荷物は一度しか選ぶことができない。
「N ≦ 30」、「全てのi(1 ≦ i ≦ N) について 1 ≦ w_i ≦1000」、「全てのi(1 ≦ i ≦ N) について 1 ≦ v_i ≦ 1000」という 3 つの条件のうち少なくともひとつの条件が成り立つ。
入力されるデータ
N W
v_1 w_1
v_2 w_2v_W w_W
（ただし 1 ≦ N ≦ 200, 1 ≦ W ≦ 10^9）
2^n 全探索で解く方法と問題点
ではどのようにして解けばよいのでしょうか？
すべての品物について入れる入れないを考えるという全探索を行えば、その計算量は O（2^n）となります。n が小さいときは問題ありませんが、少し大きな値になると制限時間内には終わりません。
とりあえず計算量が O（2^n）になるコードは以下のようになります。
すでに N には品物の総数が、W はナップサックにいれられる品物の重さが、配列 Weights には各品物の重さが、配列 Values には各品物の価値が格納されているものとします。
再起呼び出しで i 番目以降の品物をそれらの重さの総和が u 以下になるように選んだときの価値を返すSearchメソッドを以下のように定義します。するとSearch(0, W)で解を求めることができます。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static int N = 0; static int W = 0; static int[] Weights = { }; static int[] Values = { }; static void Main() { int[] vs0 = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs0[0]; W = vs0[1]; Weights = new int[N]; Values = new int[N]; for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Values[i] = vs[0]; Weights[i] = vs[1]; } Console.WriteLine(Search(0, W)); } // i 番目以降の品物をそれらの重さの総和が u 以下になるように選んだときの価値 static int Search(int i, int u) { if (i == N) return 0; else if (u < Weights[i]) return Search(i + 1, u); else { int ret1 = Search(i + 1, u); int ret2 = Search(i + 1, u - Weights[i]) + Values[i]; return Math.Max(ret1, ret2); } } } |
メモ化再帰で速度を改善する
このコードの欠陥は計算量が O（2^n）であり、nの値が大きくなると時間がかかることです。n = 10程度であれば問題ありませんが、n = 30 を超えるとなかなか結果を返してくれなくなります。
Searchメソッドは同じ引数であれば常に同じ値を返します。ならば一度呼び出されたら計算結果をどこかに保存して同じ引数で再び呼び出された場合は計算をしないで保存しておいた値をそのまま返せば処理速度を改善できるのではないかと考えることができます。「メモ化再帰」です。
以下のコードでは2次元配列を定義して、一度呼び出されたら計算結果を保存しています。これで処理速度を改善することができます。
|
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 |
class Program { static void Main() { // N, W, Weights, Values に必要な値を格納する処理は上と同じなので省略 dp = new long[N + 1, W + 1]; // 追加（配列の範囲外にアクセスしないように注意） Console.WriteLine(Search(0, W)); } static long[,] dp = { }; // i 番目以降の品物をそれらの重さの総和が u 以下になるように選んだときの価値 static long Search(int i, long u) { if(dp[i, u] != 0) return dp[i, u]; // メモされているならこれを返す if (i == N) return 0; else if (u < Weights[i]) return Search(i + 1, u); else { dp[i + 1, u] = Search(i + 1, u); // 計算結果をメモ dp[i + 1, u - Weights[i]] = Search(i + 1, u - Weights[i]); long ret1 = dp[i + 1, u]; long ret2 = dp[i + 1, u - Weights[i]] + Values[i]; return Math.Max(ret1, ret2); } } } |
漸化式を使った解法
漸化式を使った解法もあります。
2次元配列を宣言し、dp[i + 1][w] を i 番目までの品物の中から重さが w を超えないように選んだときの、価値の総和の最大値とします。
dp[i + 1][w] は dp[i][w] と dp[i][w – Weights[i]] + Values[i] を比較して大きいほうを採用します。dp[i][w] は i 番目の品物を入れない場合、dp[i][w – Weights[i]] + Values[i] は i 番目の品物を入れることで重量が w – Weights[i] から w へと増え、価値も Values[i] だけ増えた状態です。両者を比較すれば入れたほうがいいか入れないほうがいいかわかります。これによってi 番目までの品物の中から重さが w を超えないように選んだときの価値の総和の最大値も確定させることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Program { static void Main() { // N, W, Weights, Values に必要な値を格納する処理は上と同じなので省略 // Mainメソッド内部ですべて処理できるので dp はローカル変数として宣言 long[,] dp = new long[N + 1, W + 1]; for (int i = 0; i < N; i++) { for (long w = 0; w <= W; ++w) { if (w >= Weights[i]) dp[i + 1, w] = Math.Max(dp[i, w - Weights[i]] + Values[i], dp[i, w]); else dp[i + 1, w] = dp[i, w]; } } Console.WriteLine(dp[N, W]); } } |
部分和問題
N 問の問題があるコンテストがあり、i 問目の問題の配点は p_i 点である。コンテスタントは、この問題の中から何問か解き、解いた問題の配点の合計が得点となる。このコンテストの得点は何通り考えられるか。
入力されるデータ
N
p_1 p_2 p_3 … p_N（ただし 1 ≦ N ≦ 100, 1 ≦ p_i ≦ 100）
入力されるデータの制約から満点をとっても10000点を超えることはありません。そこで new bool[N + 1, 10010] を宣言します。DP[i][p]には i 番目まで見て p 点を取ることが可能かを格納します。
dp[i – 1, p] が true なら当然 dp[i, p] も true です。また i 問目の問題の配点は values[i] である以上、あらたに dp[i – 1, p + values[i – 1] ] も true になります。最後に dp[N, 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 27 28 29 30 31 32 33 34 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] values = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); // DPループDP[i][p]: i 番目まで見て p 点を取ることが可能か（可能 1、不可能 0） bool[,] dp = new bool[N + 1, 10010]; dp[0, 0] = true; for (int i = 1; i <= N; ++i) { for (int p = 0; p <= 10000; p++) { if (dp[i - 1, p]) { dp[i, p] = true; dp[i, p + values[i-1]] = true; } } } int ans = 0; for (int i = 0; i <= 10000; i++) { if (dp[N, i]) ans++; } Console.WriteLine(ans); } } |
これは全探索っぽいやり方です。最初は1問も解いていないので0点です。そのあと i問目が終わったときに得点が加算された場合とされなかった場合についてリストに得点を格納しています。得点が同じだった場合に内側のループで二重に格納しないように check 配列で確認しています。一応、処理は制限時間以内に終わります。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] values = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); List<int> list = new List<int>(); list.Add(0); foreach (int value in values) { bool[] check = new bool[10010]; List<int> newList = new List<int>(); foreach (int elm in list) { if (!check[elm]) { newList.Add(elm); check[elm] = true; } if (!check[elm + value]) { newList.Add(elm + value); check[elm + value] = true; } } list = newList; } Console.WriteLine(list.Count()); } } |
重さ以外の制約がついたナップサック問題
高橋くんは、画面のスクリーンショットを表計算ソフトに貼り付ける作業を命じられました。 画面のスクリーンショットは N 枚あり、高さは全て等しいのですが、幅が異なります。 また、表計算ソフトに貼りつけ可能なスクリーンショットには 2 つの制約が存在します。
表計算ソフトの幅は W しかない。そのため貼りつけるスクリーンショットの幅の合計値は W 以下でなければなりません。また枚数制限もあります。表計算ソフトは K 枚より多くのスクリーンショットを貼りつけることができません。よって貼りつけ可能なスクリーンショットは K 枚までです。
さらに、スクリーンショットには「重要度」が存在するため、高橋くんは 2 つの制約を満たしながら、貼り付けるスクリーンショットが持つ重要度の合計値を最大化したいです。 しかし、彼にとってこの仕事は難しいので、あなたが彼の代わりに表計算ソフトに貼り付け可能なスクリーンショットが持つ重要度の合計の最大値を求めてください。
入力されるデータ
W
N K
A_1 B_1
A_2 B_2
…
A_N B_N（ただし 1 ≦ W ≦ 10000, 1 ≦ N ≦ 50, 1 ≦ K ≦ N,
1 ≦ A_i ≦ 1000, 1 ≦ B_i ≦ 100）
ナップサック問題に重さだけでなく選べる数の制約がついた感じの問題です。2次元配列ではなく3次元配列をつかった漸化式を考えます。
dp[i][k][w]:(A[i] ,B[i])の組までで k 組選んだとき、A の総和が w の時の B の総和の最大値
3次元配列なので三重ループを回すことになります。最後に dp[N][j][w] のなかから最大値を探して結果を返します。計算量は O(NKW)です。
|
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 |
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[i][j][w]:(A[i], B[i])の組までで j 組選んだとき，Aの総和がwの時のBの総和の最大値 int[,,] dp = new int[N + 1, N + 1, W + 1]; for (int i = 0; i < N; i++) { for (int k = 0; k <= K; k++) { for (int w = 0; w <= W; w++) { dp[i + 1, k, w] = Math.Max(dp[i + 1, k, w], dp[i, k, w]); if (k + 1 <= K && w + A[i] <= W) dp[i + 1, k + 1, w + A[i]] = Math.Max(dp[i + 1, k + 1, w + A[i]], dp[i, k, w] + B[i]); } } } int ans = 0; for (int j = 0; j <= N; j++) { for (int w = 1; w <= W; w++) ans = Math.Max(ans, dp[N, j, w]); } Console.WriteLine(ans); } } |
これは全探索っぽいやり方です。
スクリーンショットを追加しないのであればそのまま、statusesに格納されているオブジェクトをループのなかで新しいリストに引き渡し、追加する場合は個数と幅の制限をこえないことを確認して、個数と価値を増やしたオブジェクトを新しく生成して追加しています。このとき同じ個数で同じ幅のオブジェクトがすでに存在するならリストには追加しないで値の更新だけをおこなっています。
同じ個数で同じ幅のオブジェクトが存在するかどうかは2次元配列 olds で確認しています。これを忘れると制限時間内に終わらないうえにメモリーをどか食いして散々な目に遭います。一応、処理は制限時間以内に終わります。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Status { public int Width = 0; public int Count = 0; public int Value = 0; } 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]; } List<Status> statuses = new List<Status>(); statuses.Add(new Status() { Count = 0, Width = 0, Value = 0, }); for (int i = 0; i < N; i++) { List<Status> newStatuses = new List<Status>(); // このループのなかで同じ個数で同じ幅のオブジェクトが生成されないようにチェックする Status[,] olds = new Status[W + 1, K + 1]; foreach (Status status in statuses) { Status old = olds[status.Width, status.Count]; if (old == null) // ないなら生成 { olds[status.Width, status.Count] = status; newStatuses.Add(status); } else if (old.Value < status.Value) // 存在し価値を更新する必要があるなら更新 { old.Value = status.Value; } if (status.Count + 1 > K) continue; if (status.Width + A[i] > W) continue; int newWidth = status.Width + A[i]; int newValue = status.Value + B[i]; int newCount = status.Count + 1; old = olds[newWidth, newCount]; if (old == null) // ないなら生成 { Status newStatus = new Status() { Count = newCount, Width = newWidth, Value = newValue, }; olds[newWidth, newCount] = newStatus; newStatuses.Add(newStatus); } else if (old.Value < newValue) // 存在し価値を更新する必要があるなら更新 { old.Value = newValue; } } statuses = newStatuses; } Console.WriteLine(statuses.Max(_ => _.Value)); } } |
