1. 2018 (2)
2. 2017 (4)
3. 2015 (9)

# 0-1 Knapsack Problem Sample Implementation

C++ Algorithm Snippet

Posted on Aug 1

### Problem Statement

The 0-1 knapsack problem: find the maximum profit $$p$$ below, by choosing items to put in the knapsack whose capacity is given by $$w$$. There are $$n$$ items and each item $$i,\ (1\leq i\leq n)$$ has a weight $$w_i$$ and a decision variable $$x_i$$ that takes 1 if the item $$i$$ is selected or 0 otherwise.

\begin{align*} & && p = \max_{1\leq i\leq n}{p_i x_i} \\ & \text{subject to} && \sum_{i = 1}^n{w_i x_i} \leq w \\ & && x_i \in \left\{0, 1\right\} \end{align*}

### Input

The format of the problem input for the above code is:

• [The capacity of the knapsack (w)] [The number of items (n)]
• For each item[k] (k = 1, 2, …, n) in turn:
• [Weight] [Profit]

### Dynamic Programing

The code above implements psuedo-polynomial time algorithm using dynamic programming. Assuming that $$\mathrm{dp}_{{i - 1},\ {x}}$$ holds the solution of the smaller problem with $$n = i - 1$$ and $$w = x$$, the solution for $$n = i$$ and $$w = x$$ can be given by the following formula.

$\mathrm{dp}_{i,\ x} = \begin{cases} \mathrm{dp}_{{i - 1},\ x} & \mbox{if } x \lt w_i \\ \min\left\{ \mathrm{dp}_{{i - 1},_ x} ,\ \mathrm{dp}_{{i - 1},\ {x - w_i}} + p_i \right\} & \mbox{if } x \geq w_i \end{cases}$

And obviously $$\mathrm{dp}_{0,\ x} = 0$$.

The solution is $$\mathrm{dp}_{n,\ w}$$.

### Backtracking

The indices of chosen items in the optimal solution can be obtained by backtracking the above algorithm.

• Initialize $$x \leftarrow w$$.
• If $$\mathrm{dp}_ {n,\ x} \neq \mathrm{dp}_ {{n - 1},\ x}$$, the item $$n$$ was selected, so update $$x \leftarrow x - w_n$$. Leave $$x$$ unchanged otherwise.
• If $$\mathrm{dp}_ {{n - 1}, x} \neq \mathrm{dp}_ {{n - 2}, x}$$, the item $$n - 1$$ was selected, so update $$x \leftarrow x - w_ {n - 1}$$. Leave $$x$$ unchanged otherwise.

2015 My gh-pages