0-1-Knapsack Problem

Definition

0-1-Knapsack Problem

The 0-1-Knapsack problem is the family of selection problems built from a 0-1-Knapsack instance

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

and binary selection variables $x\in \{0,1{\}}^n$. A selection is feasible exactly when

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

The restriction $x_i\in \{0,1\}$ means that item $i$ is either omitted or selected once; items cannot be split or reused. The standard forms are the profit-maximisation problem and the decision problem.

What 0-1 means

The terms describe independent aspects of the problem:

$$\begin{array}{cl}\text{0-1}& x_i\in \{0,1\}:\text{each item is selected at most once}\\ \text{optimisation or decision}& \text{find the best profit, or test a target }P\\ \text{binary or unary encoding}& \text{how the numerical fields are written}\end{array}$$

Both the profit-maximisation problem and the decision problem impose the same $0$-$1$ selection restriction. Their inputs may independently use a binary or unary instance encoding.