0-1-Knapsack Instance

Definition

0-1-Knapsack Instance

A 0-1-Knapsack instance consists of a finite sequence of $n$ items and a capacity $W\in \mathbb{N}$:

$$I=((w_1,p_1),\dots ,(w_n,p_n),W),$$

where $w_i\in \mathbb{N}$ is the weight and $p_i\in \mathbb{N}$ is the profit of item $i$.

A feasible solution is a vector $x\in \{0,1{\}}^n$ satisfying

$$\sum _{i=1}^n{w}_i{x}_i\le W.$$