動的計画法(1)

最近、AtCoder 版！蟻本 (初級編)をやってる。
めっちゃ多い。
多重な動的計画法の実装がうまくいったから、見せびらかそうと思って、記事を書いてる。
本当は解説しようと思ったけど、めんどくさくなった。
問題はABC015のD問題D - 高橋くんの苦悩です。
解説はAtCoder Beginner Contest 015 解説です。
pythonは通らなくて、pypyで通した。

W = int(input())
N, K = map( int, input().split())
dp = [[0 for _ in range(W+1)] for _ in range(K+1) ]
for k in range(N):
    a, b = map( int, input().split())
    for i in range(K,0,-1):
        for j in range(W,0,-1):
            if a <= j:
                dp[i][j] = max( dp[i][j], dp[i-1][j-a] + b)
print(dp[K][W])

dp[i][j]で枚数i枚以下で、幅j以下での重要度の最大値を表している。
for文を逆に回すのがポイント。