読者です 読者をやめる 読者になる 読者になる

動的計画法のお勉強と学ぶためのリソース

Algorithms DP

8月に入ったら情報オリンピックの過去問を解いてく予定なので動的計画法が使えないとどうにもならないと思い、勉強します。題材は蟻本の01ナップサック問題から

ナップサック問題


重さと価値がそれぞれw_i, v_iであるようなn個の品物があります。これらの品物から、重さの総和がWを超えないように選んだ時の、価値の総和の最大値を求めなさい。

制約:

  • 1 ≦ n ≦ 100
  • 1 ≦ w_i, v_i ≦ 100
  • 1 ≦ W ≦ 10000

Sample Input:

n = 4

(w, v) = {(2, 3), (1, 2), (3, 4), (2, 2)}

W = 5

Sample Output:

7 (0, 1, 3番の品物を選ぶ)

まずは全探索


dfs(i, j) := i番目以降の品物から重さの総和がj以下を選んだときの価値の最大値

として再帰させていきます。nが10を超えたあたりから目に見えて遅くなると思います。このままメモ化ができます。

int n, W
int w[MAX_N], v[MAX_N];

int dfs(int i, int j){
  int res = 0;
  if(i == n){
    res = 0;
  }else if(j < w[i]){
    res = dfs(i+1, j);
  }else{
    res = max(dfs(i+1, j), dfs(i+1, j-w[i]) + v[i]);
  }
  return res;
}

メモ化再帰で解く


上の全探索ではdfs(3, 2)とかdfs(4, 2)が何度も呼ばれる事態が発生するので、一度計算した結果は配列にメモしておいて二度目からは配列を読んで値を返すようにします。

int n, W;
int w[MAX_N], v[MAX_N];
int dp[MAX_N+1][MAX_N+1];

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);
  else res =  max(dfs(i+1, j), dfs(i+1, j-w[i]) + v[i]);
  return dp[i][j] = res;
}

dpで解く


メモ化再帰からdpの形にします。 漸化式は

dp[0][j] = 0;

dp[i+1][j][j] = {dp[i]j, max(dp[i][j], dp[i][j-w[i]]+v[i])}

でいいのかな。

int dp[MAX_N+1][MAX_W+1];
int n, W;
int w[MAX_N], v[MAX_N];

void dp(){

  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][j-w[i]] + v[i]);
    }
  }
  return;
}

こんな感じで解いていきます。基本的な動的計画法の問題はナップサック問題の応用で解けるらしいです。

今回のコードはGithubにのせてます

動的計画法を学ぶリソース


TopCoderチュートリアルからslideshareまでいろいろまとめてあります。

動的計画法を学ぶリソース・練習問題まとめ-フリーフォーム フリークアウト

DP := DAG上の最短経路を求める

DPの話-aizuzia

情報オリンピック予選を突破するために

動的計画法の問題を機械的に解く方法-yukobaのブログ

slide share 165ページに及ぶ大作

アルゴリズムイントロダクション 15章 動的計画法