Knapsack Problems

Why

Suppose we want to fill up a backpack by selecting from various objects which gives us differing amounts of comfort. We only have so much space in the backpack.

Definition

Number the objects $1, \dots , n$. Model the amount of space needed for a subset $H \subset \set{1, \dots , n}$ of the $n$ items by $s(H)$; here $s: \powerset{S} \to \R _+$. Model the comfort (or value) they provide by $v(H)$; here $v: \powerset{\set{1,\dots , n}} \to \R $. Given a space constraint $c$, we want to find $H \subset P$ to

\[ \begin{aligned} \text{maximize} & \quad v(H) \\ \text{subject to } & \quad s(H) \leq c \\ \end{aligned} \]

In other words, find the susbet of items which will fit in the bag and maximize the value. Such problems are called knapsack problems.

Linear formulation

It is natural to expect the space constraint to be additive In other words $H \cap G = \varnothing$ means $s(H \cup G) = s(H) + s(G)$, from which we conclude that the function is monotonic (using the fact that it is nonnegative). I.e., given $G \subset H$, we have $s(G) \leq S(H)$. Suppose we also model the value function as additive. Given $H \cap G = \varnothing$, then $v(H \cup G) = v(H) + v(G)$.

It turns out that additivity is sufficient to have a linear representation for both $s$ and $v$. For $H \subset P$, denote by $\chi _H: P \to \set{0,1}$ the characteristic function of $H$. In other words, $\chi _H$ is defined by

\[ x_H(i) = \begin{cases} 1 & \text{ if } i \in H \\ 0 & \text{ otherwise } \end{cases} \]

Then there exists $p: \set{1, \dots , n} \to \R $ and $w: \set{1, \dots , n} \to \R _+$ such that

\[ \textstyle v(H) = \sum_{i = 1}^{n} p(i) \chi _H(i) \quad \text{for all } H \subset \set{1, \dots , n} \]

and

\[ s(H) = \sum_{i = 1}^{n} w(i) \chi _H(i) \quad \text{for all } H \subset \set{1, \dots , n} \]

We can formulate the following problem: given $c \in \R _+$, $w: \set{0,1} \to \R _+$ and $p: \set{0,1}^n \to \R $, find $H \subset \set{1, \dots , n}$ to

\[ \textstyle \begin{aligned} \text{maximize} & \quad \textstyle \sum_{i = 1}^{n} p(i) \chi _{H}(i) \\ \text{subject to} & \quad \textstyle \sum_{i = 1}^{n} w_i \chi _{H}(i) \leq c \end{aligned} \]

It is common to identify $\chi _H$ with a list $x \in \{0,1\}^n$ and to find $x$ to

\[ \textstyle \begin{aligned} \text{maximize} & \quad \textstyle \sum_i p_i x_i \\ \text{subject to} & \quad \textstyle \sum_i w_i x_i \leq c \\ & \quad x_i \in \{0,1\} \text{ for all i } = 1, \dots , n \\ \end{aligned} \]

This problem is often called the zero-one knapsack problem (or 0-1 knapsack problem). The problem data is the triple $(p, w, c)$.

Alternative perspectives

Suppose instead the $n$ objects are investments, the $i$th investment requiring $w_i$ investment, returning $p_i$. Given that we have $c$ dollars in capital, how should we allocate the funds to the investments to maximize return.

Other areas in which these problems are used as models include capital budgeting, cargo loading

Terminology

We generally refer to the $n$ items, the $i$th such item having weight $w_i$ and profit $p_i$. Sometimes such problems are called single knapsack problems (one container), in contrast with multiple knapsack problems (in which there are multiple containers).