AOJ DPL_1 C Combinatorial 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; }