大容量unbounded knapsackのeventual linearity
最大密度item以外の総使用量を剰余と交換論で有限に界し、小容量prefixだけをDPした後の巨大capacityを基準itemの反復で埋める。
この典型を扱う単元: 大容量unbounded knapsackのeventual linearity
検索別名: best-density item、eventual linearity knapsack、大容量unbounded knapsack
未知問からこの典型を見つける手掛かり
- 扱う対象
- huge capacity
- small integer weights
- unbounded items
- 使う手掛かり
- best value/weight item
- capacityがDP不能に大きい
- 非基準itemを有限回へ交換
- 保つ不変量
- linear tail
- non-best total weight is bounded
- prefix residue collision
- 求めるもの
- 巨大capacityの最大価値
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: DP状態と遷移
関連する典型
学習成果と学習単位
剰余の鳩の巣原理と密度交換で非基準itemの使用量を界し、有限prefix DPと最大密度itemの反復から巨大capacityの最適値を求められる。
大容量unbounded knapsackのeventual linearityで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。