AOJ DPL_1 A Combinatiorial 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; }