動的計画法入門 - 徒然々草

この記事は「競プロ!!」競技プログラミング Advent Calendar 2017の25日目の記事です。

はじめに

動的計画法(DP : DynamicProgramming)は競プロでよく出てくるアルゴリズムのうちの一つです。しかしながら、割と難しいので分かりにくい部分でもあります。JOIの予選でもDPができなかったために、通過できなかった人も多いと思います。そこで、今回はできるだけ初心者（僕も含め）にも分かりやすいように、基本からまとめておこうと思います。

はじめの一歩

はじめの問題として、あまりにも有名なのがナップザック問題だと思います。解ける人は飛ばしてもらった方がいいかもしれません。
今回はAOJのサイトの問題を解こうと思います。Knapsack Problem

まず、始めに全探索をしてみましょう。

int dp(int n, int m){ //n個目までの品物を選び、合計の重さがm
	if(n == N) return 0;
	if(m >= W) return -100000;
	else return std::max(dp(n + 1, m + w[n]) + v[n], dp(n + 1, m));
}

各問題を選択するかしないかの二択なので、O(N²)となり現実的ではありません。（オーダの計算に関しては他のサイトを参考にしてください。）しかし、ここで少し考えると同じ引数が与えられ、同じ結果が出ることがありえます。なので、その結果を変数に保存して置けばかなり早くなることがわかります。

int memo[100][10000]; //-1で初期化をしておいてください。

int dp(int n, int m){
	if(memo[100][10000] != -1) return memo[n][m];
	if(n == N) return 0;
	if(m >= W) return -100000;
	else return memo[n][m] = std::max(dp(n + 1, m + w[n]) + v[n], dp(n + 1, m));
}

これをメモ化再起といい、動的計画法と呼べるものになりましたが、一般的には動的計画法と言うと、以下のようなものになります。

int dp[100][10000] = {}; //dp[i][j] = i番目を選び、合計でjの重さになった時の価値の合計の最大値。

for(int i = 1; i < N; ++i){
	for(int j = 0; j < W; ++j){
		dp[i][j] = dp[i - 1][j];
		if(j + w[i - 1] < W) dp[i][j + w[i - 1]] = std::max(dp[i][j + w[i - 1]], dp[i][j] + v[i - 1]);
	}
}

int ans = 0;
for(int i = 0; i < W; ++i){
	ans = std::max(ans, dp[N - 1][j]);
}

こんな感じです。表をイメージしてもらうと分かりやすいと思います。

いろいろな問題

ナップザック問題はDPの問題の中でも一番基本的なな問題です。他にも何個か問題があるので、参考までに載せておきます。

まとめ

これはあくまで動的計画法の基本なので、もっともっと動的計画法には難しい問題があります。もしかしたら、そのうち、応用編みたいなのも作るかもしれません。