ABC015 D - 高橋くんの苦悩

問題原文

atcoder.jp

解法

ナップサック問題発展版。「個数」という制約が追加されている。
やり方はいろいろあると思うんですが、 がなんか嫌な予感がしたので、「価値に対する最小の重さ」っぽくやりました。
詳しくは実装がわかりやすいかと。

実装

ちょっとサボっている。
PyPy3で700ms、142MBぐらい。
直前の配列だけ持つようにすれば想定解でもMLEしないのかな。しらんけど。

W = int(input())
N, K = map(int, input().split())
Items = [list(map(int, input().split())) for _ in range(N)]
MAX_V = 50 * 100
INF = 10 ** 9

# dp[i][k][v] := i番目まで見てk個選んだ時に価値の総和がvになるために必要な最小幅合計
dp = [[[INF] * (MAX_V + 1) for j in range(K + 1)] for i in range(N + 1)]
dp[0][0][0] = 0
for i, (a, b) in enumerate(Items):
  for k in range(K + 1):
    for v in range(MAX_V + 1):
      dp[i + 1][k][v] = min(dp[i + 1][k][v], dp[i][k][v])
      if v + b <= MAX_V and k + 1 <= K:
        dp[i + 1][k + 1][v + b] = min(dp[i + 1][k + 1][v + b], dp[i][k][v] + a)

ans = 0
for k in range(K + 1):
  for v in range(MAX_V + 1):
    if dp[-1][k][v] <= W:
      ans = max(ans, v)
print(ans)

感想

サクッと解けたけど、数ヶ月前は手も足も出なかっただろうな。。。
dpは成長を感じられてうれしい。