Definition
Binary-encoded 0-1-Knapsack Instance
A binary-encoded 0-1-Knapsack instance is a 0-1-Knapsack instance whose numerical fields
, , , and, for the decision problem, are represented in binary within a binary instance encoding. Its encoded length is where the final term is omitted for the profit-maximisation problem. The
term accounts for the item boundaries. In particular, the capacity field has length , so may be exponential in the length of that field.