資源・容量DP

概要

資源軸knapsack DP

容量・時間・個数などの有界資源を軸に選択の価値を更新する。

考え方

処理済みの品物数と使用資源量を状態にする。各品物を高々一度使うなら、同じ品物の遷移結果を入力に再利用しないよう配列を分けるか容量を降順に更新する。

価値最大化で「重さちょうどt」を表すならdp[0]=0、t>0は−∞とする。0/1品物(w,v)はtを容量Kからwへ降順に dp[t]=max(dp[t],dp[t−w]+v) と更新する。入力側t−wを今の品物で更新する前に読むので一回しか使わない。無制限品物でw>0なら逆に昇順で更新し、その品物を繰り返し使った状態から延長する。上限Kなら最後にmax_{t≤K}dp[t]、ちょうどKならdp[K]を返す。

無制限の重さ0で正価値なら上へ非有界。有限個の0/1品物で重さ0なら、別配列から一回だけ遷移する方法が定義を保つ。個数を数える場合は、品物種を外ループにする組合せと、容量を外ループにする順序付き列を区別する。

成立条件と計算量

N品物・容量K・定数遷移ならO(NK)。これはKの値に比例する擬多項式であり、巨大なKには使えない。重さ0、到達不能の番兵、負の評価、ちょうどKと高々Kの違いを固定する。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。個数・容量を軸とするナップサック型DPを実装し、更新方向を説明する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 動的計画法。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dp-subset-resource

習得する技能

  • 資源軸の上限と更新順を選び、選択の重複を避けられる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 最小十分状態からDPを設計する。

このUnitを直接前提とする単元: 大容量unbounded knapsackのeventual linearity、資源DPを引数で渡すHLRecDP。

最小十分状態を設計できるようになった後、選択数・容量・費用などの資源軸で遷移を表し、0/1選択と無制限選択の更新方向を区別する。

このUnitでは扱わないもの

  • 使用済み要素集合そのものを状態とし、容量・個数の値軸を持たないDP。

根拠