公開日

2016/07/05

最終更新

2018/11/14

記事区分

一般公開

部分問題を解きまくって、問題を解く手法です。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;
}

まっちゃん

優しくしてください

記事の執筆者にステッカーを贈る

有益な情報に対するお礼として、またはコメント欄における質問への返答に対するお礼として、記事の読者は、執筆者に有料のステッカーを贈ることができます。

さらに詳しく →

Feedbacks

ログインするとコメントを投稿できます。

ダウンキャスト (C++をもう一度)
実行時型情報 RTTI #include <iostream> #include <typeinfo> using namespace std; class MyClass { public: virtual ~MyClass() {} // typeid で正しい RTTI // (RunTime Type Information; 実行時型情報) ...
低レイヤ大好き人間4/30/2017に更新
0
- C++
競技プログラミングの基本処理チートシート (C++)
限られた時間の中で問題を解くために必要となる、競技プログラミングにおける基本的な処理のチートシートです。競プロにおけるメジャー言語 C++ を利用します。その際 C++11 の機能は利用せず C++03 の機能の範囲内で記述します。頻度高く定期的に開催されるコンテスト AtCoder Codeforces main.cpp #include <iostream>
Tamachi10/4/2021に更新
0
構造体と列挙体 (C++をもう一度)
構造体 #include <iostream> using namespace std; struct MyStruct { char charval; int intval; }; void Show(MyStruct* obj) { cout << obj->intval << endl; } int main() { ...
低レイヤ大好き人間4/25/2017に更新
0
- C++
Valgrind による C/C++ メモリリーク検出
JVM メモリリークでは JDK の jstat や jmap で原因を調査できます。C/C++ では valgrind の Memcheck ツールが利用できます。valgrind には複数のツールが含まれており既定のツールが Memcheck です。他のツールを利用する場合は --tool オプションで指定します。 [簡単な利用例](h
あおいねずみ2/27/2022に更新
0
- C++
- C言語
クラスの基本/初期化 (C++をもう一度)
構造体のように初期化する (非推奨) #include <iostream> using namespace std; const int MAX_STR = 16; class MyClass { public: int m_integer; char m_str[MAX_STR + 1]; void Show(); }; void MyClass::Show...
低レイヤ大好き人間4/25/2017に更新
0
- C++

動的計画法のサンプル

目次

ナップサック問題

dp の対象を変更

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

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

bool での dp には無駄が多い

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

記事の執筆者にステッカーを贈る

Feedbacks

関連記事