0-1 ナップサック問題

$n \in \mathbb{Z}_{\ge 1}$、重さ $w_1, \ldots, w_n \in \mathbb{Z}_{\ge 1}$、価値 $v_1, \ldots, v_n \in \mathbb{R}_{\ge 0}$、容量 $W \in \mathbb{Z}_{\ge 0}$ が与えられる。部分集合 $S \subseteq [n]$ が実行可能であるとは $w(S) = \sum_{i \in S} w_i \le W$ が成り立つことをいう。実行可能な $S$ のうち $v(S) = \sum_{i \in S} v_i$ を最大にするものを求めよ、というのが 0-1 ナップサック問題である。