2.2 The 0/1 knapsack problem

Part 1 · Combinatorial optimization problems · Chapter 2 · Chapter 2: Knapsack problems · Lecture notes, volume 1 (PDF) · Slides · Exercises: Knapsack problems · App: Brute force on the 0/1 knapsack problem

Definition 2.1: 0/1 Knapsack Problem

Given:

1. a knapsack of capacity \(c \in \Z_{\ge 1}\),

2. a set \(\mathscr{I} = \{1,2,\dots,n\}\) of \(n\) items,

3. for each item \(j \in \mathscr{I}\), a profit \(p_j \in \Z_{\ge 1}\) and a weight \(w_j \in \Z_{\ge 1}\),

the 0/1 Knapsack Problem (KP) asks to decide which items to insert into the knapsack, so that the total weight of the selected items does not exceed the knapsack capacity, and the total profit of the selected items is maximized.

• A KP instance is specified by:

  1. two integer numbers:

     • the number of items \(n \in \Z_{\ge 1}\),

     • the knapsack capacity \(c \in \Z_{\ge 1}\),

  2. two vectors of integer numbers of length \(n\):

     • \(\vet{p} \in \Z_{\ge 1}^n\), containing the item profits,

     • \(\vet{w} \in \Z_{\ge 1}^n\), containing the item weights.

• A KP feasible solution is a subset of items

  \[ S \subseteq \mathscr{I} \]

  such that the total weight of the selected items does not exceed the knapsack capacity, namely

  \[ \sum_{j\in S} w_j \le c . \]

  Accordingly, the KP can be equivalently stated as the problem of selecting a subset of items whose total weight respects the knapsack capacity, and whose total profit is maximized.

  Given a KP instance, the KP can be formally stated as:

  \[\begin{equation*} \label{KP} \tilde{S}\in \arg\max_{S \subseteq \mathscr{I}} \left\{~~ \sum_{j \in S} p_j \;\;:\;\; \sum_{j \in S} w_j \le c ~~\right\}. \tag{2.1} \end{equation*}\]

Example 2.1: KP instance

We consider a knapsack of capacity \(c = 9\) and a set \(\mathscr{I} = \{1,2,3,4,5,6\}\) of \(6\) items (\(n = 6\)), with the following profits and weights:

Items		\(j = 1\)	\(j = 2\)	\(j = 3\)	\(j = 4\)	\(j = 5\)	\(j = 6\)
Profits	\(p_j\)	\(6\)	\(5\)	\(8\)	\(9\)	\(6\)	\(7\)
Weights	\(w_j\)	\(2\)	\(3\)	\(6\)	\(7\)	\(5\)	\(9\)

In the drawing, the knapsack is a box of length \(c=9\) and every item is a block of length \(w_j\). The items \(1\) and \(4\) fill the knapsack, with weight \(9\) and profit \(15\); the other items stay out (dashed).

We call this KP instance Example 2.1: it is the reference instance of the chapter.

2.2.1 Assumptions

• We make the following assumptions:

  1. The total weight of all items exceeds the knapsack capacity (otherwise, all items could be selected). Formally:

     \[ \sum_{j \in \mathscr{I}} w_j > c \]

  2. Each item individually fits into the knapsack (otherwise, it cannot be selected). Formally:

     \[ w_j \le c,~~~~ \forall j \in \mathscr{I} \]

2.2.2 Counting the solutions, a first solution and a simple bound

• Candidate solutions. Every subset of \(\mathscr{I}\) is a candidate solution, so there are \(2^n\) of them (Chapter 1 «Combinatorial optimization problems»). For Example 2.1 we have \(2^6 = 64\).

• Feasible solutions. The three lightest items weigh \(2+3+5 = 10 > 9\), so no subset with three or more items is feasible. The feasible solutions are the empty set, the \(6\) singletons and the \(6\) pairs of the following table: \(13\) solutions out of \(64\).

pair \(S\)	\(\{1,2\}\)	\(\{1,3\}\)	\(\{1,4\}\)	\(\{1,5\}\)	\(\{2,3\}\)	\(\{2,5\}\)
weight	\(5\)	\(8\)	\(9\)	\(7\)	\(9\)	\(8\)
profit	\(11\)	\(14\)	\(\mathbf{15}\)	\(12\)	\(13\)	\(11\)

• A first solution, by eye. Item \(4\) has the largest profit (\(9\), weight \(7\)). The residual capacity \(9-7=2\) is enough for item \(1\) (weight \(2\), profit \(6\)). The subset \(\{1,4\}\) has weight \(9\) and profit \(15\): it is a primal bound, \(\LB = 15 \le z(I)\).

Observation 2.2: cardinality bound

Let \(\bar k\) be the largest integer such that the \(\bar k\) lightest items weigh at most \(c\). Every feasible subset has at most \(\bar k\) items, hence \(z(I)\) is at most the sum of the \(\bar k\) largest profits.

Proof

A subset with \(k\) items weighs at least as much as the \(k\) lightest items. If \(k > \bar k\), the \(k\) lightest items weigh more than \(c\), so the subset is not feasible. The profit of a subset with at most \(\bar k\) items is at most the sum of the \(\bar k\) largest profits. □

• A first dual bound. In Example 2.1 we have \(\bar k = 2\), since \(2+3 = 5 \le 9\) and \(2+3+5 = 10 > 9\). The two largest profits are \(9\) and \(8\), so \(\UB = 17\). The sum of all the profits, \(41\), is a much weaker dual bound.

• The gap. We have \(15 \le z(I) \le 17\): the absolute gap is \(2\) and the relative gap is \(\tfrac{2}{15}\). Listing the \(13\) feasible subsets shows that \(\{1,4\}\) is the unique optimal solution and \(z(I) = 15\); for larger instances we need stronger bounds, which come from relaxations (module Integer linear programming, Chapter 2 «Primal and dual bounds»).

---

Next: 2.3 The subset sum problem