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
, and a target profit : Question: does there exist a selection vector
such that Equivalently, the question is whether the optimal value of the corresponding profit-maximisation problem is at least
.