動的計画法練習 その1
一度蟻本を読んでいたんだけど、動的計画法が全く使いこなせないので改めて練習。
そのときのメモとコードを備忘録としてのせておく。
0-1 Knapsack Problem | Aizu Online Judge
* 基本的な 01 knapsack。
* ループの方向を変えないといけないのはどんなときだっけ？と思って dp 再利用版と通常版の二種を実装して比較。
* dp を再利用しない場合は、前回の結果を引き継ぐ操作が必要。
* dp 再利用バージョンは自動で引き継ぐけど、ループの方向を間違えるとバグる。
class b_0_1_knapsack { public: void solve_A(void) { int N, W; cin>>N>>W; vector<pair<int,int>> items; REP(i, N) { int v, w; cin>>v>>w; items.emplace_back(v,w); } // dp[i][j] := i 番目までの品物で重さの総和が j までのときの価値の総和の最大値 vector<vector<int>> dp(N+1, vector<int>(W+1,0)); REP(i, N) REP(j, W+1) { int v, w; tie(v, w) = items[i]; if (j >= w)// 前の結果 dp[i][j] との比較が必要なことに注意! dp[i+1][j] = max(dp[i][j], dp[i][j-w]+v); // max({dp[i+1][j], ...}) がいらないのは // (i+1,j) がこの (i,j)からの遷移しかないため // あってもよい else dp[i+1][j] = dp[i][j]; // 前の結果を引き継ぐ } cout<<dp[N][W]<<endl; } // weight のループを逆方向に void solve_B(void) { int N, W; cin>>N>>W; vector<pair<int,int>> items; REP(i, N) { int v, w; cin>>v>>w; items.emplace_back(v,w); } vector<vector<int>> dp(N+1, vector<int>(W+1,0)); REP(i, N) for (int j = W; j >= 0; --j) { int v, w; tie(v, w) = items[i]; if (j >= w) dp[i+1][j] = max(dp[i][j], dp[i][j-w]+v); else dp[i+1][j] = dp[i][j]; } cout<<dp[N][W]<<endl; } // solve_A の dp 再利用バージョン void solve_C(void) { int N, W; cin>>N>>W; vector<pair<int,int>> items; REP(i, N) { int v, w; cin>>v>>w; items.emplace_back(v,w); } vector<int> dp(W+1,0); REP(i, N) { int v, w; tie(v, w) = items[i]; // for (int j = w; j <= W; ++j) のように // 逆方向のループでは現在の i での更新結果を利用してしまうのでダメ for (int j = W; j >= w; --j) dp[j] = max(dp[j], dp[j-w]+v); } cout<<dp[W]<<endl; } void solve(void) { //solve_A(); //solve_B(); solve_C(); } };
0-1 Knapsack Problem | Aizu Online Judge
* 個数制限なし knapsack。
* dp 再利用版では 01 knapsack とループが逆になる。
class c_knapsack { public: void solve_A(void) { int N, W; cin>>N>>W; vector<pair<int,int>> items; REP(i, N) { int v, w; cin>>v>>w; items.emplace_back(v,w); } vector<vector<int>> dp(N+1,vector<int>(W+1,0)); // a_coin_changing と同じ // dp[i+1][j] = max(dp[i+1][j], max{dp[i][j-k*w[i]]+v[i]*k | k>=0}) O(N*W^2) // = max(dp[i+1][j], dp[i][j], max{dp[i][(j-w[i])-(k-1)*w[i]]+v[i]*(k-1)+v[i] | k>=1}) // = max(dp[i+1][j], dp[i][j], dp[i+1][j-w[i]]+v[i]) REP(i, N) for (int j = 0; j <= W; ++j) { int v, w; tie(v, w) = items[i]; if (j-w>=0) dp[i+1][j] = max({dp[i+1][j], dp[i][j], dp[i+1][j-w]+v}); else dp[i+1][j] = max(dp[i+1][j], dp[i][j]); } cout<<dp[N][W]<<endl; } // dp テーブル再利用バージョン // weight のループの方向に注意!! void solve_B(void) { int N, W; cin>>N>>W; vector<pair<int,int>> items; REP(i, N) { int v, w; cin>>v>>w; items.emplace_back(v,w); } vector<int> dp(W+1,0); REP(i, N) { int v, w; tie(v, w) = items[i]; for (int j = w; j <= W; ++j) { // solve_A のループ部分を見ればわかるように dp[i+1][j-w] は i での weight のループ // 更新結果を参照している。よって weight のループの方向は増加方向 // これは 01-knapsack とは逆になっていることに注意!! dp[j] = max({dp[j], dp[j-w]+v}); } } cout<<dp[W]<<endl; } void solve(void) { //solve_A(); solve_B(); } };
Longest Increasing Subsequence | Aizu Online Judge
* dp の持ち方を変えて二分探索するのがポイント
// Longest Increasing Subsequence class d_lis { public: // MLE(TLE) してしまうケース O(N^2) void solve_MLE(void) { int N; cin>>N; vector<int> a; REP(i, N) { int x; cin>>x; a.push_back(x); } // dp[i][j] := i 番目の文字まででできる LIS の最後の数字のインデクスが j であるときの長さの最大値 vector<vector<int>> dp(N+1, vector<int>(N, 0)); REP(i, N) { REP(j, i+1) dp[i+1][j] = 1; // j番目の文字だけの部分列の長さは 1 なので for (int j = 0; j < i; ++j) { // 前の結果を引き継ぐ dp[i+1][j] = max(dp[i+1][j], dp[i][j]); // 更新できそうなら更新。末尾に a[i] をつなげる if (a[j] < a[i]) dp[i+1][i] = max(dp[i+1][i], dp[i][j]+1); } } int ans = 0; REP(j, N) ans = max(ans, dp[N][j]); cout<<ans<<endl; } // dp テーブルを再利用する version O(N^2) void solve_TLE(void) { int N; cin>>N; vector<int> a; REP(i, N) { int x; cin>>x; a.push_back(x); } // dp[j] := LIS の最後の数字のインデクスが j であるときの長さの最大値 vector<int> dp(N, 0); REP(i, N) { // dp テーブルを再利用しているので、前回までの結果は自動でひきつがれている dp[i] = 1; // i番目の文字だけの部分列の長さは 1 なので for (int j = 0; j < i; ++j) // j==i にならないのでループの方向はどっちでもよい { // 更新できそうなら更新。末尾に a[i] をつなげる if (a[j] < a[i]) dp[i] = max(dp[i], dp[j]+1); } } int ans = 0; REP(j, N) ans = max(ans, dp[j]); cout<<ans<<endl; } // // 高速化版 // O(N*log(N)) // void solve_optim(void) { int N; cin>>N; vector<int> a; REP(i, N) { int x; cin>>x; a.push_back(x); } const ll inf = (1<<30); // 同じ長さの部分列なら最後の数値が小さい方がよい // dp[j] := 長さが j+1 のときの部分列の最後値 // として dp する vector<ll> dp(N+1, inf); REP(i, N) { // この dp を更新していくと、 dp が単調増加列になること // から二分探索が使える *lower_bound(RANGE(dp), a[i]) = a[i]; } cout<<lower_bound(RANGE(dp), inf)-dp.begin()<<endl; } void solve(void) { //solve_MLE(); //solve_TLE(); solve_optim(); } };
Edit Distance (Levenshtein Distance) | Aizu Online Judge
* 編集距離とかいうやつ
class e_levenshtein { public: void solve(void) { const int inf = (1<<30); string s1,s2; cin>>s1>>s2; int N = s1.length(); int M = s2.length(); // // * 1文字削った文字列の末尾にどのような文字を追加すれば一致するか見ることで、 // 1文字削った文字列との距離から1文字加えた文字列との距離を求めることができる // * 長さ 0 の文字列と長さ x の文字列の距離は x である // // dp[i][j] := s1[0...i] を s2[0...j] の編集距離 vector<vector<int>> dp(N+1, vector<int>(M+1, inf)); // 片方が空のときは挿入のコストのみ REP(j, M+1) dp[0][j] = j; REP(i, N+1) dp[i][0] = i; FOR(i, 1, N+1) FOR(j, 1, M+1) { int cost = (s1[i-1] == s2[j-1])? 0 : 1; dp[i][j] = min({ dp[i-1][j]+1, // s1 の文字の削除してから編集 dp[i][j-1]+1, // s2 の文字の削除してから編集 dp[i-1][j-1] + cost}); // 文字の置換 } cout<<dp[N][M]<< endl; } };
