AOJ DPL_1 A Combinatiorial 0-1 Knapsack Problem

問題

0-1 Knapsack Problem

解法

dp[i][j] := i番目までの荷物でjまでの重さを入れた時に価値の最大値

漸化式

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

DPで解きます。典型問題。問題の下に解説があるので参照。

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

int main(){
  scanf("%d%d", &N, &W);
  rep(i, N) scanf("%d%d", v+i, w+i);

  rep(i, N) rep(j, W+1){
    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]);
  }

  printf("%d\n", dp[N][W]);
  return 0;
}