DP E
指定された制限重量以下で価値を最大化するナップサック問題
しかし重量を定義域とするDPをするには、制限重量の空間が広すぎる
値域と定義域の交換をして、価値を定義域、その価値を達成する最小重量を値とするDPをやる
from 動的計画法
DP_E
問題文 E - Knapsack 2
重量の空間が10^11
価値の空間が10^5
DP_Dでは重量を定義域として価値の関数をつくり、最大値を求めた
この問題ではそのアプローチでは定義域が広すぎる
そこで逆に価値を定義域として重量の関数を作る
そして定義域の中で重量が制約を満たす最大の添字を見つける
pythondef 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 iRelated Pages
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×arc106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×unionfind×mod_pでの組み合わせ×Educational DP Contest×動的計画法×atcoder_library_practice_contest×atcoder_library×帰着する力×帰着訓練→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]