DP E
E - Knapsack 2
指定された制限重量以下で価値を最大化するナップサック問題
しかし重量を定義域とするDPをするには、制限重量の空間が広すぎる
値域と定義域の交換をして、価値を定義域、その価値を達成する最小重量を値とするDPをやる
from 動的計画法
DP_E
問題文 E - Knapsack 2
値域と定義域の交換
重量の空間が10^11
価値の空間が10^5
DP_Dでは重量を定義域として価値の関数をつくり、最大値を求めた
この問題ではそのアプローチでは定義域が広すぎる
そこで逆に価値を定義域として重量の関数を作る
そして定義域の中で重量が制約を満たす最大の添字を見つける
https://gyazo.com/8f6820c6fa358d709bd62c806b3166fb
code:python
def solve(N, W, WV):
MAX_VALUE = N * 10 ** 3
weights = INF * (MAX_VALUE + 1)
weights0 = 0
for i in range(N):
next_weights = weights:
weight, value = WVi
for j in range(MAX_VALUE - value + 1):
next_weightsj + value = min(
weightsj + value,
weightsj + weight)
weights = next_weights
for i in range(MAX_VALUE, -1, -1):
if weightsi <= W:
return i