Unary-encoded 0-1-Knapsack Instance

Definition

Unary-encoded 0-1-Knapsack Instance

A unary-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 unary within a unary instance encoding. Using a self-delimiting representation such as $z\mapsto 1^{z}0$, its encoded length is

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

where the final term is omitted for the profit-maximisation problem. The item count $n$ is exposed by the sequence structure rather than stored as another numeric parameter. In particular, the input contains $\Theta (W)$ symbols for the capacity, so iterating over all capacities $0,1,\dots ,W$ is polynomial in the encoded input length.