2014-07-24から1日間の記事一覧

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…

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][MA…

AOJ DPL_1 A Combinatiorial Coin Changing Problem

問題 Coin Changing Problem 解法 DPのプラクティスのセットのところの問題ですので当然DP。普通にDPを組むと何枚でも使用できるってのkを使用枚数の上限としてO(nmk)ってなるので間に合わない。たぶん正答率が低いのはこれでTLEが出てるからかと。 dp[i+1][…