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*} \]

Sample Implementation

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