ナップサック問題

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

入力として品物の集合$~I=\{1,2,\ldots,N\}~$とナップサックの容量$~W~$が与えられるものとします。 各品物$~i \in I~$には重み$~w_{i}~$と価値$~v_{i}~$があるものとします。選択する品物を表す決定変数$~x_{i}~$を定義します。$x_{i}~$は品物$~i \in I~$を選択する場合に$~1$、それ以外の場合に$~0~$を取るように設定します。このとき、ナップサック問題を数式で表現すると以下のようになります。

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

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