動的計画法のお勉強と学ぶためのリソース - シュレーディンガーの(ry 揉んでみるまで柔らかいかどうかは分からない

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;
}