labs.wakayama.ninja
ナップサック問題
限られた容量にどの品物を入れると価値が最大になるかを、DP表で追います。
ナップサック問題とは
各品物には重さと価値があります。容量を超えないように品物を選び、価値の合計をできるだけ大きくします。
品物を入れない
max
品物を入れる
容量
8
DP表
品物
選ばれた品物
まだ計算中です。
合計重さ
0
合計価値
0
眺め方
行は「どの品物まで使えるか」、列は「容量がいくつか」を表します。各マスには、その条件で得られる最大価値が入ります。
いま見ているマスでは、品物を入れない値と、入れられるなら入れた値を比べます。大きい方がそのマスの答えです。