A. ナップザック問題とは？
ナップザックに荷物を詰める場合についての問題です．各荷物の容積（または，重さ）とその価値が与えられたとき，ナップザックの容量（または，ナップザックに詰めることができる最大重量）を超えずに荷物を詰めるときに，それらの荷物の合計価値が最大となる組み合わせを求める問題です．ここでは，各荷物の重量及び価値と，ある容器に詰めることができる最大重量を与え，最大となる合計価値を求める問題とします．
B. 遊び方
パズルの実行を開始すると，以下に示すような画面が表示されます．
荷物の数として，10 または 20 を選択し，「ゲーム開始」ボタンをクリックすると，以下に示すような画面が表示されます．左側が荷物の数が 10 の場合，右側が荷物の数が 20 の場合を表しています．なお，荷物の数が 10 の場合に対しては，初期状態ではなく，2 つの荷物を容器に移動した場合を表しています．
荷物を容器（下側の四角の部分）に入れるには，容器の上にある荷物を単にクリックするだけです．また，容器内の荷物を外に出すには，容器内の荷物をクリックすることによって可能です．容器に入れた荷物の合計重量が画面の上に示してある「容器の最大許容重量」を超えない範囲で，価値の合計が最大になるように，適当に荷物を移動してください．荷物の移動を行うと，その時点における容器内の合計重量，及び，その価値が画面の下部に表示されます．さらに，最適値を達成すると，「最適解です！」というメッセージが画面の下部に表示されます．なお，最適値は一つですが，容器に入れる荷物の組合せは一意であるとは限りません．
コメント