EDPC - D - Knapsack 1

【類題】EDPC - E - Knapsack 2 - 競プロはじめました

考え方②：「ぴったり」で考える方法

「$W$以下」ではなく，「$W$ぴったり」となるように考えるのがよくあるパターン．また，ぴったりを考えたほうが，遷移が考えやすい（勘違いしにくい）．
【例】

• ABC219D - Strange Lunchbox - 競プロはじめました

$N$コから選んで重さが$W$（ぴったり）になるときの価値の最大値を$f(N, W)$とする．もし，$0\leq n \leq N -1$，$0\leq w \leq W - 1$について$f(n, w)$がわかっていれば，$f(N, W)$が計算できる．よって，DPで計算できる．具体的には，$n$コ目を選ばない場合と選ぶ場合を考えて
【貰うDP】

\begin{aligned}
f(n, w)
=\max\{f(n - 1, w), f(n - 1, w - w_{n}) + v_{n} \}
\end{aligned}

【配るDP】

\begin{aligned}
\begin{cases}
\, f(n + 1, w) = \max\{f(n + 1, w), f(n, w) \} \\
\, f(n + 1, w + w_{n})
=\max\{f(n + 1, w + w_{n}), f(n, w) + v_{n} \}
\end{cases}
\end{aligned}

である．

答えは

\begin{aligned}
\max \{f(N, w) \mid 0\leq w \leq W\}
\end{aligned}

である．

貰うDP

INF = 1 << 60

N, W = map(int, input().split())
WV = [tuple(map(int, input().split())) for _ in range(N)]

dp = [[-INF] * (W + 1) for _ in range(N + 1)]
dp[0][0] = 0
for n in range(N):
  for w in range(W + 1):
    wn, vn = WV[n]
    dp[n + 1][w] = dp[n][w]
    if w - wn >= 0:
      dp[n + 1][w] = max(dp[n + 1][w], dp[n][w - wn] + vn)
      
print(max(dp[N]))

考え方①：「以下」で考える方法

答えを求めるdpを直接作る方法．通常，ナップサック問題の回答はこっちで解かれている．

$f(N, W)$を答えとする（つまり，$W$以下！）．$0\leq n \leq N -1$，$0\leq w \leq W - 1$について$f(n, w)$がわかっていれば，$f(N, W)$が計算できる．よって，DPで計算できる．具体的には，$n$コ目を選ばない場合と選ぶ場合を考えて
【貰うDP】

\begin{aligned}
f(n, w) = \max\{f(n - 1, w), f(n - 1, w - w_{n}) + v_{n}\}
\end{aligned}

【配るDP】

\begin{aligned}
\begin{cases}
\, f(n + 1, w) = \max\{f(n + 1, w), f(n, w) \} \\
\, f(n + 1, w + w_{n})
=\max\{f(n + 1, w + w_{n}), f(n, w) + v_{n} \}
\end{cases}
\end{aligned}

である．

よって，考え方②と全く同じ遷移になる．ただし，初期化の方法が異なる（-INFではなくゼロで初期化すれば，初期化も同じになる）．

貰うDP

INF = 1 << 60

N, W = map(int, input().split())
WV = [tuple(map(int, input().split())) for _ in range(N)]

dp = [[-INF] * (W + 1) for _ in range(N + 1)]
dp[0] = [0] * (W + 1)
for n in range(N):
  for w in range(W + 1):
    wn, vn = WV[n]
    dp[n + 1][w] = dp[n][w]
    if w - wn >= 0:
      dp[n + 1][w] = max(dp[n + 1][w], dp[n][w - wn] + vn)
      
print(dp[N][W])