Binary-encoded 0-1-Knapsack Instance

Definition

Binary-encoded 0-1-Knapsack Instance

A binary-encoded 0-1-Knapsack instance is a 0-1-Knapsack instance whose numerical fields $w_i$, $p_i$, $W$, and, for the decision problem, $P$ are represented in binary within a binary instance encoding. Its encoded length is

$$\left|{\mathrm{enc}}_{\mathrm{bin}}(I)\right|=\Theta \left(n+\sum _{i=1}^n(\log (w_i+1)+\log (p_i+1))+\log (W+1)+\log (P+1)\right),$$

where the final term is omitted for the profit-maximisation problem. The $n$ term accounts for the item boundaries. In particular, the capacity field has length $\Theta (\log (W+1))$, so $W$ may be exponential in the length of that field.