ナップサック問題

ナップサック問題とは、容量があるナップサックの中にいくつかの品物を詰め込み、入れた品物の総価値を最大にするという問題です。

入力として品物の集合とナップサックの容量が与えられるものとします。 各品物には重みと価値があるものとします。選択する品物を表す決定変数を定義します。は品物を選択する場合に、それ以外の場合にを取るように設定します。このとき、ナップサック問題を数式で表現すると以下のようになります。

上記の式を満たす場合に最小値をとるように、 イジングモデルのエネルギー関数を以下のように定義します。

ここでは、ナップサックの容量を設定してシミュレーションを体験できます。