EDPC - E - Knapsack 2

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

考え方

まず，制約から何を変数に使えるか考える．

D - Knapsack 1とは，制約のみ異なる．これにより，変数に$W$を使うことはできなくなる．代わりに，$v_{i}$が小さくなっているので，$N, v_{i}$を変数とすることを考える．

D - Knapsack 1	E - Knapsack 2
\begin{aligned} \begin{cases} \, 1\leq N \leq 100 \\ \, 1\leq W \leq \textcolor{blue}{10^{5}} \\ \, 1\leq w_{i} \leq W \\ \, 1\leq v_{i} \leq \textcolor{red}{10^{9}} \end{cases} \end{aligned}	\begin{aligned} \begin{cases} \, 1\leq N \leq 100 \\ \, 1\leq W \leq \textcolor{red}{10^{9}} \\ \, 1\leq w_{i} \leq W \\ \, 1\leq v_{i} \leq \textcolor{blue}{10^{3}} \end{cases} \end{aligned}

ある重さ以下で価値を最大化する問題なので，ある価値を実現する最小重さがわかったときに答えが求められないか考える．

• 価値の小さい順に見ていき，重さが$W$を超えたら，超える前の価値を出力する

などの方法で求めることができる（*1）．

これにより，D - Knapsack 1とほとんど同じ問題になった．違うのは，

• 価値と重さが入れ替わった
• 最大値ではなく最小値を求める問題になった

という点．

DP - 「ぴったり」で考える方法

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

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

【配るDP】

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

である．

貰うDP

INF = 1 << 60
vmax = 10 ** 5  # vi_max * N_max

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

dp = [[INF] * (vmax + 1) for _ in range(N + 1)]
dp[0][0] = 0
for n in range(N):
  for v in range(vmax + 1):
    wn, vn = WV[n]
    dp[n + 1][v] = dp[n][v]
    if v - vn >= 0:
      dp[n + 1][v] = min(dp[n + 1][v], dp[n][v - vn] + wn)

for v in range(vmax + 1):
  if dp[N][v] <= W:
    ans = v
print(ans)

*1:最小重さは価値の単調増加関数となり，bisectで求められるかと思ったが，①dpテーブルで初期値のまま更新されていないものを除く必要がある，②「ぴったり」で考えた場合には必ずしも単調増加にならない，に注意が必要．特に，②から，「ぴったり」でdpを作る場合はbisectでは求められない．