ナップサック問題
I = { 1 , 2 , ⋯ , N } {\displaystyle I=\{1,2,\cdots ,N\}} を品物の集合とし、各品物 i ∈ I {\displaystyle i\in I} の重みを w i {\displaystyle w_{i}} 、価値を v i {\displaystyle v_{i}} 、品物の重量の合計の上限を W {\displaystyle W} とするとき、次のようにあらわされるものをナップサック問題という。
max ∑ i ∈ I v i x i s . t . ∑ i ∈ I w i x i ≤ W x i ∈ N ( ∀ i ∈ I ) {\displaystyle {\begin{array}{lll}\max &\sum _{i\in I}v_{i}x_{i}&\\\mathrm {s.t.} &\sum _{i\in I}w_{i}x_{i}\leq W&\\&x_{i}\in \mathbb {N} &(\forall i\in I)\end{array}}}
ここで、 x i {\displaystyle x_{i}} はナップサックへ入れる品物の個数を表している。