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