ひとりで勝手にはじめた蟻本読書会 動的計画法 最長共通部分列問題 蟻本読書会の続きです。
部分和問題とは
「{1, 3, 7, 10, 13} の部分和で、和が 21 になるものは存在するか？」という問題です。この場合、{1, 7, 13}を選ぶと和は 21 になります。部分和問題は動的計画法で解くことができます。
部分和は何通り存在するか？
部分和が指定された値になる場合は何通り存在するか？
部分和が指定された値になる場合で選ぶ個数の最小値は？
部分和が指定された値になる場合で選ぶ個数を指定された個数以内にする方法は何通り存在するか？
などを求めることができます。
部分和が指定された値になる場合は何通り存在するか？
1 ～ N の番号がついた N 個のおもりがあり、おもり i の重さは A_i です。
おもりを何個か選んで重さの和が X となるようにする方法が何通りあるか求めてください。なお、同じおもりを2個以上選ぶことはできません。重さが同じおもりが複数存在する場合、それらは区別して別のものとして扱うことにします。
答えは非常に大きくなる可能性があるので、答えを 1,000,000,007 で割った余りで出力してください。
N X
A_1
A_2
…
A_Nただし、
N はおもりの個数（1 ≦ N ≦ 100）
X は目標とする重さの和（1 ≦ X ≦ 1,000）
A_i はおもり i の重さ（1 ≦ A_i ≦ 100）
int[,] dp = new int[N + 1, X + 1]; dp[i + 1, k] を A[i]までを選択するしないを決めたあとで k になる場合の数と定義します。すると処理を開始する前はなにも選択されていないのと、そのような場合の数は 1 とおりだけしか存在しないので dp[0, 0] = 1; となります。また dp[i, k] ＞ 0 となる k が存在する場合、A[i] を選択する場合は dp[i + 1, k + A[i]] += dp[i, k];、しない場合は dp[i + 1, k] += dp[i, k];と遷移します。このとき k + A[i] が X を超えてしまうと配列の範囲外のアクセスになってしまうので注意します。
答えを 1,000,000,007 で割った余りで出力するため、dpに加算処理をおこなったときは 1,000,000,007 の剰余をとります。最後に dp[N, X] が解となります。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, X; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; X = vs[1]; } int[] A = new int[N]; for (int i = 0; i<N; i++) A[i] = int.Parse(Console.ReadLine()); // dp[i + 1, k] : A[i]までを選択して k になる場合の数 int[,] dp = new int[N + 1, X + 1]; dp[0, 0] = 1; int mod = 1000000007; for (int i = 0; i < N; i++) { for (int k = 0; k <= X; k++) { if (dp[i, k] == 0) continue; // dp[i, k] > 0 となる k を探して・・・ // A[i] を加算しても k が X を超えないなら加算する if (k + A[i] <= X) { dp[i + 1, k + A[i]] += dp[i, k]; dp[i + 1, k + A[i]] %= mod; } // A[i] を加算しない場合も考える dp[i + 1, k] += dp[i, k]; dp[i + 1, k] %= mod; } } Console.WriteLine(dp[N, X]); } } |
部分和が指定された値になる場合で選ぶ個数の最小値は？
1 ～ N の番号がついた n 個のおもりがあり、おもり i の重さは A_i です。
おもりを何個か選んで重さの和が x となるようにする方法を考えたとき、選ぶおもりの個数の最小値を出力してください。なお、同じおもりを2個以上選ぶことはできません。
なお、重さの和が x となるようにおもりを選ぶ方法が存在しない場合は -1 と出力してください。
入力されるデータ
N X
A_1
A_2
…
A_NN はおもりの個数（1 ≦ N ≦ 100）
X は目標とする重さの和（1 ≦ X ≦ 1,000）
A_i はおもり i の重さ（1 ≦ A_i ≦ 100）
この問題では dp[i + 1, k] を A[i]までを選択して k になる選択された個数と定義します。また最初はなにも選ばれていないので 0 個です。なので dp[0, 0] = 0 であり、それ以外の部分は int.MaxValue で初期化します。
あとは dp[i, k] が int.MaxValue ではない k を探して
|
1 2 |
dp[i + 1, k + A[i]] = dp[i, k] + 1; // A[i] を選択するので個数が 1 増える dp[i + 1, k] = dp[i, k]; // 選択しないので個数は変化しない |
の処理をおこないますが、右辺が左辺に代入されるのは 左辺よりも右辺が小さいときだけです。
|
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 N, X; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; X = vs[1]; } int[] A = new int[N]; for (int i = 0; i<N; i++) A[i] = int.Parse(Console.ReadLine()); // dp[i + 1, k] : A[i]までを選択して k になる選択された個数 int[,] dp = new int[N + 1, X + 1]; for (int i = 0; i <= N; i++) { for (int k = 0; k <= X; k++) dp[i, k] = int.MaxValue; } dp[0, 0] = 0; for (int i = 0; i < N; i++) { for (int k = 0; k <= X; k++) { if (dp[i, k] == int.MaxValue) continue; if (k + A[i] <= X) { if(dp[i + 1, k + A[i]] > dp[i, k] + 1) dp[i + 1, k + A[i]] = dp[i, k] + 1; } if (dp[i + 1, k] > dp[i, k]) dp[i + 1, k] = dp[i, k]; } } if(dp[N, X] < int.MaxValue) Console.WriteLine(dp[N, X]); else Console.WriteLine(-1); } } |
1 ～ N の番号がついた N 種類のおもりがあり、おもり i の重さは A_i です。それぞれのおもりは無限個存在しており、任意のおもりを任意の個数使うことができます。このとき、おもりを選んで重さの和を x となるようにすることができるかどうか判定してください。
入力されるデータ
N X
A_1
A_2
…
A_NN はおもりの個数（1 ≦ N ≦ 100）
X は目標とする重さの和（1 ≦ X ≦ 1,000）
A_i はおもり i の重さ（1 ≦ A_i ≦ 100）
同じおもりを複数回使用できるので、漸化式の遷移が少し変わります。
これまでは、A[i] を選択する場合は dp[i + 1, k + A[i]] = dp[i, k];、しない場合は dp[i + 1, k] = dp[i, k];と遷移させてきました。
今回は同じおもりを複数回使用できるので、A[i] を M 回選択する場合は配列の範囲外へのアクセスに注意しながら
dp[i + 1, k + A[i] * 1] = dp[i, k];
dp[i + 1, k + A[i] * 2] = dp[i, k];
…
dp[i + 1, k + A[i] * M] = dp[i, k];
とやりたくなりますが、これだと計算量が増えてしまいます。
では、どうすればよいのでしょうか？
A[i]を選択したあともA[i]を選択することができるので、
A[i] を選択しない場合： dp[i + 1, k] = dp[i, k];
A[i] を選択する場合： dp[i, k + A[i]] = dp[i, k]; // i はそのまま
とするのです。これだと計算量を抑えることができます。
|
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, X; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; X = vs[1]; } int[] A = new int[N]; for (int i = 0; i < N; i++) A[i] = int.Parse(Console.ReadLine()); // dp[i + 1, k] : A[i]までを選択して k になるかどうか？ bool[,] dp = new bool[N + 1, X + 1]; dp[0, 0] = true; for (int i = 0; i < N; i++) { for (int k = 0; k <= X; k++) { if (dp[i, k] == false) continue; // dp[i, k] > 0 となる k を探して・・・ // A[i] を加算しても k が X を超えないなら加算する if (k + A[i] <= X) dp[i, k + A[i]] = dp[i, k]; // A[i] を加算しない場合も考える dp[i + 1, k] = dp[i, k]; } } if(dp[N, X]) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } |
部分和 応用問題
D – Cooking
高橋君は料理 1 から N の N 品の料理を作ろうとしています。料理 i はオーブンを連続した T_i 分間使うことで作れます。1 つのオーブンを 2 つ以上の料理のために同時に使うことはできません。
2 つのオーブンを使えるとき、N 品の料理を全て作るまでに最短で何分かかりますか？ なお、オーブンを使う時間以外は無視できるものとします。
入力されるデータ
N
T_1 T_2 … T_N
（ただし、1 ≦ N ≦ 100, 1 ≦ T_i ≦ 10^3 ）
それぞれのオーブンの使用時間は料理をつくる順番には関係ありません。重要なのはそのオーブンにどの料理を割り振るかです。また 2 つのオーブンを使うのであれば、料理をすべて作るまでにかかる時間を T_i の総和（S）の半分未満にすることは絶対にできません。
そこでこの問題は「T の部分和で S / 2 以上になるものの最小値は？」と読み替えることができます。
dp[i + 1, k] を A[i]までを選択して総和を k にできるか？と定義します。最後に dp[N, i] == true である i を取得します。そのなかから S / 2 以上である最初の i を見つければよいのです。単純に S / 2 を計算すると S が奇数の場合切り捨てが起きるので注意します。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); // dp[i + 1, k] : A[i]までを選択して総和を k にできるか？ int S = A.Sum(); bool[,] dp = new bool[N + 1, S + 1]; dp[0, 0] = true; for (int i = 0; i < N; i++) { for (int k = 0; k <= S; k++) { if (!dp[i, k]) continue; if (k + A[i] <= S) dp[i + 1, k + A[i]] = dp[i, k]; dp[i + 1, k] = dp[i, k]; } } int half; // half >= S / 2 を満たす最初の整数 if (S % 2 == 0) half = S / 2; else half = S / 2 + 1; int ans = 0; for (int i = 0; i <= S; i++) { if (dp[N, i] && i >= half) { ans = i; break; } } Console.WriteLine(ans); } } |
最長増加部分列問題
N 本の木が横一列に並んでいます。左から i 番目の木を木 i と呼ぶことにします。木 i の高さは a_i です。
あなたは、何本かの木を伐採することによって、残った木を左から順に見ると高さが単調増加になっているようにしたいと考えています。つまり、残った木を左から 木 k_1, 木 k_2, … , 木 k_m とすると、a_{k_1} < a_{k_2} < ... < a_{k_m} が満たされているようにしたいです。なるべく多くの木が残るように、伐採する木を工夫して選んだとき、伐採されずに残る木の本数が最大でいくつになるか求めてください。 なお、最初から N 本の木が単調増加に並んでいる場合は、1 本も伐採しなくてよいものとします。 入力されるデータ N A_1 A_2 ... A_N （ただし、1 ≦ n ≦ 5,000 1 ≦ a_i ≦ 1,000,000,000 ）
dp[k] を、最後が木 k であるような増加部分列のうち最長であるものの長さとします。dp[1] ～ dp[k-1] が求まっているとして、dp[k] とこれらの関係はどのようになっているかを考えてみましょう。
1 以上 k 未満の i について A_i < A_k が成り立っているとき、最後が木 i であるような増加部分列の最後に木 k をくっつけることで、新しく長さ dp[i] + 1 の増加部分列を作れることがわかります。そして、最後が木 k であるような最長増加部分列は、このようにして作られる部分列のうち最長のものであることがわかります。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = new int[N]; for (int i = 0; i < N; i++) A[i] = int.Parse(Console.ReadLine()); int[] dp = new int[N + 1]; dp[0] = 1; for (int i = 1; i < N; i++) { dp[i] = 1; // 木 i のみからなる部分列の長さ for (int k = 0; k < N; k++) { // 最後が木 j であるような増加部分列の末尾に木 i をくっつける if (A[k] < A[i]) dp[i] = Math.Max(dp[i], dp[k] + 1); } } int ans = 0; for (int i = 0; i < N; i++) ans = Math.Max(ans, dp[i]); Console.WriteLine(ans); } } |
