0-1-Knapsack Decision Problem

Definition

0-1-Knapsack Decision Problem

The 0-1-Knapsack decision problem is the decision form of the 0-1-Knapsack problem.

Instance: item weights and profits, a capacity $W$, and a target profit $P$:

$$I=((w_1,p_1),\dots ,(w_n,p_n),W,P),w_i,p_i,W,P\in \mathbb{N}.$$

Question: does there exist a selection vector $x\in \{0,1{\}}^n$ such that

$$\sum _{i=1}^n{w}_i{x}_i\le W\wedge \sum _{i=1}^n{p}_i{x}_i\ge P?$$

Equivalently, the question is whether the optimal value of the corresponding profit-maximisation problem is at least $P$.