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

AOJ DPL_1 C Combinatorial Knapsack Problem

問題

Knapsack Problem

解法

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+1][j - w[i]] + v[i]);
  }
  printf("%d\n", dp[N][W]);
  return 0;
}