動的計画法のサンプル

[履歴] [最終更新] (2016/07/09 17:00:07)

プログラミング/IoT の関連商品 (Amazonのアソシエイトとして、当メディアは適格販売により収入を得ています。)

オープンソース・ソフトウェアルータVyatta入門　――実践ルーティングから仮想化まで (Software Design plus)

ESP-WROOM-02ピッチ変換済みモジュール《シンプル版》

普通のピンヘッダ10本セット

ロベールのC++入門講座

実用ロボット開発のためのROSプログラミング

星

概要

部分問題を解きまくって、問題を解く手法です。DFS 全探索とは発想が異なり、例えば i が大きい後ろからある種の全探索します。部分問題の結果をメモリに格納 (メモ化) しておき、より大きな部分問題を解くときに利用します。

問題文を図にしてみる
i の大きい後ろに限定した部分問題を見つける
i 番目を「とれる (とる, とらない), とれない」で場合分けして漸化式を得る
端が定数 (0 など) になる表を書いてみる (すべての矢印が指す先が問題の答え)
(冗長な計算を除外することで計算量を落とす)

ナップサック問題

重さ w_i, 価値 v_i の品物 N 個から、重複を許さず重さの総和が W を越えないように選んだときの価値の総和の最大値を求める。

in.txt

main.cpp

#include <iostream>
using namespace std;

const int MAXN = 1024;

int N,W;
int v[MAXN];
int w[MAXN];

// 定義 dp[i][j]
// i, i+1, ..., N-1 の品物を対象としたときの
// j を W に読みかえたときの「ナップサック問題」の解  ←ナップサック問題の部分問題としてのナップサック問題
int dp[MAXN][MAXN];

int main() {
    cin>>N>>W;
    for(int i = 0; i < N; ++i) cin>>w[i]>>v[i];

    fill((int*)dp, (int*)(dp+MAXN), 0); // グローバル変数は 0 で初期化されるため不要ではありますが、解法のイメージ把握のため。

    // 後ろから (ある種の) 全探索を開始。
    for(int i = N-1; i >= 0; --i) {
        for(int j = 0; j <= W; ++j) {
            if(j >= w[i]) { // i 番目の品物をと*れ*る
                dp[i][j] = max(v[i] + dp[i+1][j-w[i]], dp[i+1][j]); // 品物をとる, とらない
            }
            else { // とれない
                dp[i][j] = dp[i+1][j];
            }
        }
    }
    cout << dp[0][W] << endl;

    return 0;
}

dp の対象を変更

W が非常に大きな値で max(v_i) が比較的小さな値の場合は dp の対象を変更すると計算時間を短縮できます。

#include <iostream>
using namespace std;

#define INF 1e9

const int MAXN = 100;
const int MAXV = 100; // 比較的小さな max(v_i)

int N,W;
int v[MAXN];
int w[MAXN];

// 定義 dp[i][j]
// i, i+1, ..., N-1 の品物を対象としたときの
// 価値の総和が j になるような重さの総和の最小値。
// 「ナップサック問題」の解 res は max(j | dp[0][j] <= W)
int dp[MAXN+1][MAXV*MAXN + 1]; // 初項の "+1", ゼロスタートの "+1" (重要)

int main() {
    cin>>N>>W;
    for(int i = 0; i < N; ++i) cin>>w[i]>>v[i];

    fill((int*)dp, (int*)(dp+MAXN), INF);
    dp[N][0] = 0; // 0 個の品物から価値の総和が 0 になるように 0 個を選ぶと重さは 0 になる。

    // 後ろから (ある種の) 全探索を開始。
    for(int i = N-1; i >=0; --i) {
        for(int j = 0; j <= MAXV*N; ++j) {
            if(j >= v[i]) { // i 番目の品物をと*れ*る
                dp[i][j] = min(w[i] + dp[i+1][j-v[i]], dp[i+1][j]); // 品物をとる, とらない
            }
            else { // とれない
                dp[i][j] = dp[i+1][j];
            }
        }
    }

    // max(j | dp[0][j] <= W)
    for(int j = MAXV*N; j >= 0; --j) {
        if(dp[0][j] <= W) {
            cout << j << endl;
            break;
        }
    }
    return 0;
}

最長共通部分列 (Longest Common Subsequence; LCS)

文字列 {s_i} と {t_j} の共通部分文字列 {s_ik} == {t_jl} の最大長を求める。ここで、部分文字列とは ik < i(k+1) および jl < j(l+1) ということ。

in.txt

AGGTAB
GXTXAYB

main.cpp

#include <iostream>
#include <string>
using namespace std;

const int MAXN = 1024;

int Ls,Lt;
string s,t;

// 定義 dp[i][j]
// s_i, s_{i+1}, ..., s_{Ls - 1} の文字列と
// t_j, t_{j+1}, ..., t_{Lt - 1} の文字列に関する
// 「最長共通部分列」の解  ← 最長共通部分列の部分問題としての最長共通部分列
int dp[MAXN][MAXN];

int main() {
    cin>>s>>t;
    Ls = s.size();
    Lt = t.size();

    fill((int*)dp, (int*)(dp+MAXN), 0); // グローバル変数のため不要な処理。イメージ把握のため。
    for(int i = 0; i < Ls; ++i) dp[i][Lt] = 0;
    for(int j = 0; j < Lt; ++j) dp[Ls][j] = 0;

    // 後ろから (ある種の) 全探索を開始。今度は 2 変数。
    for(int i = Ls - 1; i >= 0; --i) {
        for(int j = Lt - 1; j >= 0; --j) {
            if(s[i] == t[j]) { // 先頭の s_i と t_j をと*れ*る
                dp[i][j] = max(max(1 + dp[i+1][j+1], dp[i+1][j]), dp[i][j+1]); // s_i と t_j をとる, とらない (s_i をとらない, t_j をとらない)
            }
            else { // とれない
                dp[i][j] = max(dp[i+1][j], dp[i][j+1]); // s_i をとらない, t_j をとらない
            }
        }
    }
    cout << dp[0][0] << endl;

    return 0;
}

個数制限のないナップサック問題

重さ w_i, 価値 v_i の品物 N 種類から、重さの総和が W を越えないように選んだときの価値の総和の最大値を求める。同じ種類の品物を何個選んでもよい。

in.txt

意味合いとしての main.cpp

#include <iostream>
using namespace std;

const int MAXN = 1024;

int N,W;
int v[MAXN];
int w[MAXN];

// 定義 dp[i][j]
// i, i+1, ..., N-1 の品物を対象としたときの
// j を W に読みかえたときの「ナップサック問題」の解  ←ナップサック問題の部分問題としてのナップサック問題
int dp[MAXN][MAXN];

int main() {
    cin>>N>>W;
    for(int i = 0; i < N; ++i) cin>>w[i]>>v[i];

    fill((int*)dp, (int*)(dp+MAXN), 0); // グローバル変数は 0 で初期化されるため不要ではありますが、解法のイメージ把握のため。

    // 後ろから (ある種の) 全探索を開始。
    for(int i = N-1; i >= 0; --i) {
        for(int j = 0; j <= W; ++j) {
            if(j >= w[i]) { // 品物をと*れ*る
                for(int k = 0; k * w[i] <= j; ++k) {
                    dp[i][j] = max(v[i]*k + dp[i+1][j-(w[i]*k)], dp[i][j]); // 品物を k 個とる, とらない(k=0)
                }
            }
            else { // とれない
                dp[i][j] = dp[i+1][j];
            }
        }
    }
    cout << dp[0][W] << endl;

    return 0;
}

上記概要の 4 番で、端が定数になる表をみたときに、重複する経路である k のループを除外した main.cpp
(除外することの意味合いは考えず、表をみると計算が冗長なため除外してよいと考える)

#include <iostream>
using namespace std;

const int MAXN = 1024;

int N,W;
int v[MAXN];
int w[MAXN];

// 定義 dp[i][j]
// i, i+1, ..., N-1 の品物を対象としたときの
// j を W に読みかえたときの「ナップサック問題」の解  ←ナップサック問題の部分問題としてのナップサック問題
int dp[MAXN][MAXN];

int main() {
    cin>>N>>W;
    for(int i = 0; i < N; ++i) cin>>w[i]>>v[i];

    fill((int*)dp, (int*)(dp+MAXN), 0); // グローバル変数は 0 で初期化されるため不要ではありますが、解法のイメージ把握のため。

    // 後ろから (ある種の) 全探索を開始。
    for(int i = N-1; i >= 0; --i) {
        for(int j = 0; j <= W; ++j) { // j のループは 0 から開始する (重要)
            if(j >= w[i]) { // 品物をと*れ*る
                dp[i][j] = max(v[i] + dp[i][j-w[i]], dp[i+1][j]); // 品物を k 個とる, とらない(k=0) (結果として意味は同じ)
                //                      ↑i+1 ではない (重要)
            }
            else { // とれない
                dp[i][j] = dp[i+1][j];
            }
        }
    }
    cout << dp[0][W] << endl;

    return 0;
}

bool での dp には無駄が多い

N 種類の数 a_i がそれぞれ m_i 個あるとき、総和が K になるような選び方があるかどうか。dp を bool にして計算すると、部分問題の計算で得られた情報が落ちていくため、最終的な計算量が大きくなります。int 型にして何らかの情報を保存しながら計算すると計算量が落とせます。

in.txt

3 17  ← N,K
3 3  ← a_0, m_0
5 2
8 2

main.cpp

#include <iostream>
using namespace std;

const int MAXN = 1024;

int N,K;
int a[MAXN];
int m[MAXN];

// 定義 dp[i][j]
// i, i+1, ..., N-1 に関して
// 総和を j にできるとき: 未使用の a[i] の個数
// 総和を j にできないとき: -1
int dp[MAXN][MAXN];

int main() {
    cin>>N>>K;
    for(int i = 0; i < N; ++i) cin>>a[i]>>m[i];

    fill((int*)dp, (int*)(dp+MAXN), -1);
    for(int j = 0; j <= K; ++j) dp[N][j] = -1;
    dp[N][0] = 0;

    // 後ろから (ある種の) 全探索を開始。
    for(int i = N-1; i >=0; --i) {
        for(int j = 0; j <= K; ++j) {
            if(dp[i+1][j] >= 0) { // a[i] すべて m[i] 個が未使用な状態でスタート
                dp[i][j] = m[i];
            }
            else if(j < a[i] || dp[i][j-a[i]] <= 0) { // a[i] を使用できない、またはすべて使用済み
                dp[i][j] = -1;
            }
            else {
                dp[i][j] = dp[i][j-a[i]] - 1; // 未使用個数を -1
            }
        }
    }
    cout << (dp[0][K] >= 0 ? "Yes": "No") << endl;

    return 0;
}

最長増加部分列 (Longest Increasing Subsequence; LIS)

数列 a_0, a_1, ..., a_(N-1) の増加部分列のうち最長の数列の長さを求める。ここで、増加部分列とは i < j ならば a_i < a_j ということ。一次元の dp テーブルを利用する例です。

in.txt

main.cpp

#include <iostream>
using namespace std;

const int MAXN = 1024;

int N;
int a[MAXN];

// 定義 dp[i]
// i, i+1, ..., N-1 で考えたときの
// 先頭が a[i] であるような (重要)
// 最長増加部分列の長さ。最小値 1 です。
int dp[MAXN];

int main() {
    cin>>N;
    for(int i = 0; i < N; ++i) cin>>a[i];

    fill(dp, dp+MAXN, 0);
    dp[N] = 0; // 要素数 0 の数列からは長さ 0 の数列しか作れない。
    int res = 0;

    for(int i = N-1; i >= 0; --i) {
        dp[i] = 1; // 先頭が a[i] のみの場合からスタート
        for(int j = i+1; j < N; ++j) {
            if(a[i] < a[j]) { // 先頭が a[i] になれる。
                dp[i] = max(dp[i], 1 + dp[j]);
            }
        }
        res = max(res, dp[i]);
    }
    cout << res << endl;

    return 0;
}