[Model] Knapsack

[zazabap]

Motivation

One of Karp's 21 NP-complete problems; foundational in combinatorial optimization, cryptography, and resource allocation. Has direct reductions to ILP and QUBO.

Definition

Name: Knapsack
Reference: Karp, 1972; Kellerer, Pferschy & Pisinger, Knapsack Problems, 2004

Given $n$ items, each with weight $w_i$ and value $v_i$, and a capacity $C$, find a subset $S \subseteq {0, \ldots, n-1}$ such that $\sum_{i \in S} w_i \leq C$, maximizing $\sum_{i \in S} v_i$.

Variables

• Count: $n$ (one variable per item)
• Per-variable domain: binary ${0, 1}$
• Meaning: $x_i = 1$ if item $i \in S$ (selected)

Schema (data type)

Type name: Knapsack
Variants: 0-1 (binary), bounded, unbounded

Field	Type	Description
weights	Vec<i64>	Item weights $w_0, \ldots, w_{n-1}$
values	Vec<i64>	Item values $v_0, \ldots, v_{n-1}$
capacity	i64	Knapsack capacity $C$

Problem Size

Metric	Expression	Description
num_items	$n$	Number of items

Complexity

• Decision complexity: NP-complete (Karp, 1972)
• Best known exact algorithm: $O(nC)$ pseudo-polynomial dynamic programming; $O(2^{n/2})$ via meet-in-the-middle
• Approximation: FPTAS exists — $(1-\varepsilon)$-approximation in $O(n^2 / \varepsilon)$ time
• References: Karp 1972; Ibarra & Kim 1975 (FPTAS)

Extra Remark

Knapsack is weakly NP-hard (admits pseudo-polynomial algorithms), unlike strongly NP-hard problems such as TSP. It is a special case of ILP with a single constraint. The subset-sum problem is the special case where $v_i = w_i$. Knapsack-based cryptosystems (Merkle-Hellman) were historically important in public-key cryptography.

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to integer programming, through a new Knapsack → ILP rule issue (to be filed).

Bruteforce: enumerate all $2^n$ subsets, check capacity constraint, return maximum value.

Example Instance

$n = 4$ items, capacity $C = 7$:

Item	Weight	Value	Value/Weight
0	2	3	1.50
1	3	4	1.33
2	4	5	1.25
3	5	7	1.40

Feasible subsets:

Subset	Weight	Value
${0, 3}$	7	10
${1, 2}$	7	9
${0, 2}$	6	8
${0, 1}$	5	7
${3}$	5	7

Optimal: $S = {0, 3}$, $x = (1,0,0,1)$, weight $= 7$, value $= 10$.

Note: greedy by value/weight ratio picks item 0 (1.50) then item 3 (1.40), which happens to be optimal here, but greedy is not optimal in general.