動的計画法
動的計画法の基本的な考え方と使い方について
こんにちは,のんです.
今回は動的計画法通称DPについてです.動的計画法を使う有名な問題としてナップサック問題などがありますね.
動的計画法は値をメモしていき漸化的に問題解決を目指すものです.
ともあれ,実際に問題を解きながら学んでいきましょう.
ナップサック問題
n個の商品があり,各商品iに対して重量,価値が定められています.総重量がを超えないように商品を選ぶとき,商品の総価値の最大値を求めなさい.
制約:
#include <iostream>
#include <vector>
using namespce std;
int max_n = 100, max_W = 10000;
int dp[max_n + 1][max_W + 1];//dpテーブル
int main(){
memset(dp, -1, sizeof(dp))//初期値を-1にしてメモを初期化
int n;
cin >> n;
vector<int> w(n);
vector<int> v(n);
for (int i = 0; i < n; i++){
cin >> w[i]
cin >> v[i]
}
int W;
cin >> W;
//i番目以降の商品について総重量がj以下になるように選ぶ:jは残りの重量
int dfs(int i, int j){
if(dp[i][j] >= 0) return dp[i][j]//すでに調べてあるならば再利用
int res;//現在の総価値
if(i == n) res = 0;//ベースケース
else if (j < w[i]) res = dfs(i + 1, j);//商品iの重量が残りの重量を超える場合
else res = max(
dfs(i + 1, j), //選ばない場合
dfs(i + 1, j - w[i]) + v[i]//選ぶ場合
);//商品iがまだ入る場合で価値が大きくなるほうを選択
return dp[i][j] = res//テーブルにメモ
}
}
ここでdpテーブルについて,dp[i][j]は商品i以降の商品から総重量がj以下になるように選んだ時の総価値の最大値となっています.
そして,その値は,
として漸化式に表せる.
例えばdp[3][3]でw[3] = 2,v[3] = 2ならdp[4][3]とdp[4][3 - 2 = 1] + 2 ( = v[3])を比較して大きいほうを採用する
というようにテーブルの下から値を埋めるように遷移していく
| i\j | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | ||||||
| 1 | ||||||
| 2 | ||||||
| 3 | ||||||
| 4 |
当然,漸化式を変形することで,遷移の方向を逆にすることもできる.
最長共通部分問題
長さnの文字列Sと長さmの文字列Tが与えられる.
これら2つの共通部分文字列の長さの最大値を求めよ.
ただし,部分文字列とは文字列Sをと表すときの部分列からなる文字列である.
制約:
この問題は通称LCS(longest common subsequence)と呼ばれる問題です.
まずは,遷移について考えてみましょう.
dp[i][j]をS[1]~S[i]とT[1]~T[j]のLCSの長さとして定義しましょう.
そうすると,S[i + 1]までの文字列とT[j + 1]までの文字列の共通部分列は
- S[i + 1] = T[j + 1]ならば,S[i],T[j]にS[i + 1]をつなげたもの
- S[i]までとT[j + 1]までの共通部分列
- S[i + 1]までとT[j]までの共通部分列
のどれかでなので,
という漸化式で表すことができる.
この漸化式はであり解はdp[n][m]となる
#include <iostream>
#include <string>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
string s,t;
cin >> s >> t;
vector<vector<int>> dp(n, vector<int>(m, -1));
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(s[i] == t[j]){
dp[i + 1][j + 1] = dp[i][j] + 1;
}
else{
dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
}
}
}
cout << dp[n][m] << "\n";
return 0;
}
基本的に漸化式に従って2重ループを作るだけでよいので簡単ですね.
次は少し問題設定が難しいものを扱ってみましょう
ナップサック問題(個数制限なし)
n個の商品のうち,各商品iについてその重量を,価値をとする.これらの商品から,総重量がを超えないように商品を選ぶときの総価値の最大値を求めよ.ただし,同じ種類の商品をいくつでも選択してよいとする.
制約:
今回は重複を含めて選ぶことができます.しかし,やることは同じでとりあえず漸化式を考えることにします.
まず,dp[i + 1][j]をi番目までの商品から総重量がj以下となるように選んだ時の総価値の最大値とします.
すると漸化式は
として表せます.
この漸化式通りに愚直にコードを書くと次のようになります.
(メタ的ですがどうせ改良するので適当に書きます)
int dp[n][W];
for(int i = 0; i < n; i++){
for(int j = 0; j < W; j++){
for(int k = 0; k * w[i] <= j; k++){//j - k * w[i] >= 0が必要十分なため
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - k * w[i]] + k * v[i])
}
}
}
しかしこれだと3重ループになり,計算量は$O(n^3)で終わっている(ほぼ確実にTLE)なので改良が必要です.
ということで効率化できる部分について考えます.
漸化式について,
これで,変数を消去することができたため,2重ループにより表現可能になりました.ちなみに.計算量はです.
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> w(n);
vector<int> v(n);
for(int i = 0; i < n; i++){
cin >> w[i];
}
for(int i = 0; i < n; i++){
cin >> v[i];
}
int W;
cin >> W;
vector<vector<int>> dp(n, vector<int>(W, -1));
for(int i = 0; i < n; i++){
for(int j = 0; j <= W; j++){
if( j < w[i])dp[i + 1][j] = dp[i][j];
else {
dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);
}
}
}
cout << dp[n][W] << "\n";
}
次に,ナップサック問題について少し,制約を少し大きくしたものについて考えていきます.
ナップサック問題2
n個の商品のうち,各商品iについてその重量を,価値をとする.これらの商品から,総重量がを超えないように商品を選ぶときの総価値の最大値を求めよ.
制約:
前回と同様重さに対する価値でdpをすると計算量はなのでTLEとなります.そこで今回は価値に対する重さで計算します.
dp[i + 1][j]:i番目までの商品から総勝ちがjとなるように選んだ時の総重量の最小値(そのような値が存在しない場合は,十分大きな値INFw)
として定める.0番目までの商品は選べないので,初期値をINFとしておく.
この時,i番目までの商品から総価値がjとなるように選ぶためには,
- i-1番目までの総価値がjとなるように選ぶ
- i-1番目までの商品からの総価値がj-v[i]となるように選び,i番目の商品を加える
の2通りがある.そのため,漸化式は,次のようになる
すると計算量はとなる
#include <iostream>
#include <vector>
using namespace std;
using INF = 2 << 30;
int main(){
int n;
cin >> n;
vector<int> w(n);
vector<int> v(n);
int W;
for(int k = 0; k < 2; k++){
for(int i = 0; i < n; i++){
if(k == 0)cin >> w[i];
else if(k == 1)cin >> v[i];
}
}
int nm = n * 100
vector<vector<int>> dp(n, vector<int>( nm, INF))
dp[0][0] = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j <= nm; j++){
if(i < v[i])dp[i + 1][j] = dp[i][j];
else dp[i + 1][j] = min(dp[i][j], dp[i][j − v[i]] + w[i])
}
}
int res = 0;
for(int i = 0; i <= nml i++){
if(dp[n][i] <= W )res = i;
}
cout << res << "\n";
}