分割可能ナップサック

物品を分割できるナップサックです。価値÷重さの密度が高い順に入れ、最初の入り切らない物品を切って残容量を埋めます。連続に分割でき単位価値が一定なら密度貪欲法は最適です。分割を禁じると同じ規則は安全ではありません。

矩形の幅を重さ、高さを価値密度とすれば、面積が価値です。固定幅の棚へ高い矩形から置き、最後を縦に切ることで、各幅から得る価値を高めます。

分割可能ナップサックの仕組み

value / weight を計算して降順にします。全体が入れば全部、入らなければ重さ min(weight, remaining) を取り、価値も比例させます。満杯で終了し、一部を取った後の物品は見ません。

物品が独立、重さが正、連続分割可能、単位価値が一定というモデルです。予算、帯域、貨物への応用では条件を確認します。限界利益が変わる場合や不可分の単位では、この矩形モデルではありません。

分割が貪欲選択を安全にする理由

密度 d の重さを載せながら、未使用に d′ > d が残るなら、同じ重さの小片を高密度へ交換すると価値が増えます。分割可能なら全物品を動かさず小片だけ交換できます。こうした改善をなくすと、最高の利用可能密度から使う形になります。

画面は本番前に、最低密度の一片を最高密度の等幅の一片へ換えます。増えた面積が利益です。

0/1 では任意の小片交換ができません。密度の高い物品が埋めにくい空きを残し、後の選択を制限します。第二幕は分割を禁じ、同じ密度規則と真の整数選択の最適を比べます。

選択をステップで追う

容量 50、価値/重さは A = 120/30、B = 60/10、C = 45/15、D = 100/20。

1. 密度：A は 4.0、B は 6.0、C は 3.0、D は 5.0。最大価値の A は密度では三番目。
2. 順序：B、D、A、C。
3. 交換の検査：C の重さ 10、価値 30 を、同重量の B、価値 60 へ換える。利益 10 × (6.0 − 3.0) = 30。
4. B 全体：重さ 10 ≤ 残り 50。累積価値 60、残り 40。
5. D 全体：20 ≤ 40。価値 160、残り 20。
6. A を切る：重さ 30 に対し空き 20。min(30, 20) = 20、三分の二を取り、120 × 20/30 = 80 を加える。価値 240、空き 0。
7. 終了：C は未検討。分割解は 240。
8. 分割禁止：A の切片を戻す。全体の A は 20 の隙間に入らず飛ばし、C 全体を取る。密度貪欲法は 205。
9. 0/1 最適と比較：四物品の全 16 選択を調べると、A+D が重さ 50、価値 220。分割なし貪欲 205、0/1 最適 220、分割最適 240。一切断で、分割なし貪欲より 35 増える。

切断線は残容量の端に合い、切片の高さは元と同じです。密度を変えないためです。最後に 205、220、240 を比例する棒で比べます。

時間・空間計算量

合計 O(n log n)。整列した順序とソートの作業領域以外、走査状態は O(1) です。物品や出力の保存は別途必要です。最大一ソート、一走査です。

古典的 0/1 ナップサックの容量 DP は O(n·W) の擬多項式時間で、一般の厳密最適化は NP-hard です。分割版の貪欲法を、そのまま整数選択の多項式厳密解法にはできません。

境界ケース

• 全部入る：総重量が容量以下なら切らず、三方式が一致。All items fit では分割の利益がない。
• 最初から入り切らない：最高密度の物品より容量が小さければ、初手で分割して終了。First item cut は重さ 30 から 20 を取る。
• ぴったり：min(weight, remaining) = weight で全体を取り、切断として描かない。
• 同密度：同点内の順は総価値を変えない。入力順を保ち、Equal densities で比較する。
• 分数結果：既定の 2/3 × 120 = 80 は整数。価値 100、重さ 30 から重さ 20 を取れば循環小数で、表示は小数一桁に丸める。

よくある間違い

• 総価値で並べる。 A を先に取ると密度 4 へ容量 30 を使い、より高密度の B を待たせます。この順は 220 で、240 ではありません。
• 0/1 に流用する。 既定の分割なし密度法は 205、整数最適は 220。重さの組み合わせを順序だけでは表せません。
• 切片に全価値を付ける。 value × take/weight です。幅が減れば面積も減ります。
• 残り 0 でも続ける。 最初の部分切断で満杯です。部分的に取る物品は最大一つ。
• 浮動小数の比較を無視する。 v1 × w2 と v2 × w1 の比較なら、積が精確でオーバーフローしない範囲で除算誤差を避けられます。このトレースもそれで順序を固定します。