# ナップサック問題
:::{container} prog-cpp
重さと価値を持つアイテムの集合と,重量制限のあるナップサックが与えられたとき,**ナップサック問題**は,総重量が容量以内に収まるようにしつつ,総価値を最大化するアイテムの部分集合を選択することを目的とします.
$w_i$ と $v_i$ ($0\leq i\leq n-1$) をそれぞれアイテム $i$ の重さと価値とします.
$S\in \lbrace 0, 1, \ldots n-1\rbrace$ を選択されたアイテムの集合とします.
$$
\begin{aligned}
\text{Maximize:} & \sum_{i\in S} v_i \\
\text{Subject to:} & \sum_{i\in S} w_i \leq W
\end{aligned}
$$
ここで $W$ はナップサックの重量容量です.
## QUBO定式化
この問題をQUBOとして定式化するために,$n$ 個のバイナリ変数 $x_i\in\lbrace 0,1\rbrace$ ($0\leq i\leq n-1$) の集合 $X$ を導入します.ここで,アイテム $i$ が選択されるのは $x_i=1$ のときかつそのときに限ります.
上記の定式化は次のように書き換えられます：
$$
\begin{aligned}
\text{Maximize:} & \sum_{i=0}^{n-1} v_ix_i \\
\text{Subject to:} & \sum_{i=0}^{n-1} w_ix_i \leq W
\end{aligned}
$$
## Hi-QUBOプログラム
制約はHi-QUBOが提供する**範囲演算子**を用いて表現できます.
結果として得られるQUBO目的関数は次のように定義されます：
$$
\begin{aligned}
f(X) &= -\sum_{i=0}^{n-1} v_ix_i + P\times (0\leq \sum_{i=0}^{n-1} w_ix_i \leq W)
\end{aligned}
$$
QUBOソルバーは目的関数を最小化するため,元の最大化目的は符号を反転しています.
定数 $P$ は制約を強制するための十分大きなペナルティパラメータです.
以下のHi-QUBOプログラムは,Exhaustive Solverを用いて10個のアイテムのナップサック問題を解きます：
```{literalinclude} /../programFiles/cppPrograms/example/real/knapsack-program1.cpp
:language: cpp
:caption: knapsack-program1.cpp
```
このプログラムでは,式 `constraint` と `objective` を別々に構築し,ペナルティ係数 `1000` を用いて最終的なQUBO式 `f` に結合しています.
次に,Exhaustive Solver を `f` に適用し,すべての最適解を列挙します.
以下の出力は,エネルギー,制約値,目的関数値を含む最適解を示しています：
```{include} /../programFiles/markDown/example/real/knapsack.md
:start-after:
:end-before:
```
このインスタンスには2つの最適解があり,いずれも総価値 `480` を達成しつつ,容量制約をちょうど満たしていることがわかります.
## `qbpp::cons()` で容量制約を表す
容量制約は,同じ範囲式を `qbpp::cons()` で囲むことで制約として印を付けられます.
上のプログラムからの変更はこれだけです.`constraint` を
`qbpp::cons(0 <= qbpp::sum(w * x) <= capacity)` にするだけで,`constraint.body(sol)`
を含む残りの部分はそのままです.バンドルされたソルバーはこれを制約として扱い,
Exhaustive Solver では容量を満たす選択だけが列挙されます:
```{literalinclude} /../programFiles/cppPrograms/example/real/knapsack-program2.cpp
:language: cpp
:caption: knapsack-program2.cpp
```
このプログラムは,範囲演算子版と同じ2つの最適解を出力します:
```{include} /../programFiles/markDown/example/real/knapsack.md
:start-after:
:end-before:
```
2つの定式化は等価です.制約を `qbpp::cons()` で囲むことで,バンドルされた
ソルバーがそれを制約として扱うため,より大きなナップサック問題も扱いやすく
なります.
:::
:::{container} prog-python
重さと価値を持つアイテムの集合と,重量制限のあるナップサックが与えられたとき,**ナップサック問題**は,総重量が容量以内に収まるようにしつつ,総価値を最大化するアイテムの部分集合を選択することを目的とします.
$w_i$ と $v_i$（$0\leq i\leq n-1$）をそれぞれアイテム $i$ の重さと価値とします.
$S\in \lbrace 0, 1, \ldots n-1\rbrace$ を選択されたアイテムの集合とします.
$$
\begin{aligned}
\text{Maximize:} & \sum_{i\in S} v_i \\
\text{Subject to:} & \sum_{i\in S} w_i \leq W
\end{aligned}
$$
ここで $W$ はナップサックの重量容量です.
## QUBO定式化
この問題をQUBOとして定式化するために,$n$ 個のバイナリ変数 $x_i\in\lbrace 0,1\rbrace$（$0\leq i\leq n-1$）の集合 $X$ を導入します.ここで,アイテム $i$ が選択されるのは $x_i=1$ のときかつそのときに限ります.
上記の定式化は次のように書き換えられます：
$$
\begin{aligned}
\text{Maximize:} & \sum_{i=0}^{n-1} v_ix_i \\
\text{Subject to:} & \sum_{i=0}^{n-1} w_ix_i \leq W
\end{aligned}
$$
## PyQBPPプログラム
制約は PyQBPP が提供する**範囲演算子** `(lo <= expr) & (qbpp.same <= hi)` を用いて表現できます.
結果として得られるQUBO目的関数は次のように定義されます：
$$
\begin{aligned}
f(X) &= -\sum_{i=0}^{n-1} v_ix_i + P\times (0\leq \sum_{i=0}^{n-1} w_ix_i \leq W)
\end{aligned}
$$
QUBOソルバーは目的関数を最小化するため,元の最大化目的は符号を反転しています.
定数 $P$ は制約を強制するための十分大きなペナルティパラメータです.
以下のPyQBPPプログラムは,Exhaustive Solverを用いて10個のアイテムのナップサック問題を解きます：
```{literalinclude} /../programFiles/pythonPrograms/example/real/knapsack-program1.py
:language: python
:caption: knapsack-program1.py
```
このプログラムでは,式 `constraint` と `objective` を別々に構築し,ペナルティ係数 `1000` を用いて最終的なQUBO式 `f` に結合しています.
次に,Exhaustive Solver を `f` に適用し,すべての最適解を列挙します.
以下の出力は,エネルギー,制約値,目的関数値を含む最適解を示しています：
```{include} /../programFiles/markDown/example/real/knapsack.md
:start-after:
:end-before:
```
このインスタンスには2つの最適解があり,いずれも総価値 `480` を達成しつつ,容量制約をちょうど満たしていることがわかります.
## `qbpp.cons()` で容量制約を表す
容量制約は,同じ範囲式を `qbpp.cons()` で囲むことで制約として印を付けられます.
上のプログラムからの変更はこれだけです.`constraint` を
`qbpp.cons((0 <= qbpp.sum(w * x)) & (qbpp.same <= capacity))` にするだけで,
`sol(constraint.body)` を含む残りの部分はそのままです.バンドルされたソルバーは
これを制約として扱い,Exhaustive Solver では容量を満たす選択だけが列挙されます:
```{literalinclude} /../programFiles/pythonPrograms/example/real/knapsack-program2.py
:language: python
:caption: knapsack-program2.py
```
このプログラムは,範囲演算子版と同じ2つの最適解を出力します:
```{include} /../programFiles/markDown/example/real/knapsack.md
:start-after:
:end-before:
```
2つの定式化は等価です.制約を `qbpp.cons()` で囲むことで,バンドルされた
ソルバーがそれを制約として扱うため,より大きなナップサック問題も扱いやすく
なります.
:::