Knapsack Problems


Knapsack problem is a name to a family of combinatorial optimization problems that have the following general theme: You are given a knapsack with a maximum weight, and you have to select a subset of some given items such that a profit sum is maximized without exceeding the capacity of the knapsack. The knapsack problem is NP-hard and appears very frequently in practical, real-life situations. A dynamic programming solution for the knapsack problem runs in pseudo-polynomial time and is arguably the easiest way to approach many of these problems on a programming contest.

Types of Knapsack Problems


The 0/1 Knapsack Problem

A dynamic programming solution for the 0/1 knapsack problem is given below:

// initializations
int i, j;
int[][] P = new int[N+1][W+1];   // p[i][j] is the best profit for items 0 to i and knapsack of size j.
int[][] s = new int[N+1][W+1];   // s keeps track of which items are selected
for (i = 0; i <= N; i++)
    for(j = 0; j <= W; j++)
        s[i][j] = 0;

// trivial cases
for (i = 0; i <= N; i++) P[i][0] = 0;  // no items left
for (j = 0; j <= W; j++) P[0][j] = 0;  // no space left in knapsack

// for each item i from 1 to N:
for (i = 1; i <= N; i++) {
    // consider all knapsack sizes j from 1 to W:
    for (j = 1; j <= W; j++) {
        if (w[i-1] > j) {
            // case 1: Item i (i-1 here due to 0-indexing) does not fit in j.
            // the profit is thus the same as the best-so-far for j.
            P[i][j] = P[i - 1][j];
        } else {
            // case 2: item i (i-1 here due to 0-indexing) does fit in j.
            // decide whether using item i is profitable.
            tmp = P[i - 1][j - w[i-1]] + p[i-1];
            if (tmp > P[i-1][j]) {
                P[i][j] = tmp;
                s[i][j] = 1;
            } else {
                P[i][j] = P[i-1][j];
            }
        }
    }
}

// S[N][W] now contains the max profit.
// this code outputs the subset of the N items that led to that profit.
j = W;
for (i = N; i>= 1; i--) {
    if (keep[i][j] == 1) {
        System.out.println(i);
        j -= w[i-1];
    }
}


Number Partitioning - Partition a set S containing N integers, into two sets S1 and S2, so that |sum(L1) - sum(L2)| is minimized. This problem is perhaps even more general than the 0/1 knapsack problem and is considered by Garey and Johnson as one of the six basic NP-hard problems that lie at the heart of NP-completeness theory. It has applications in multiprocessor scheduling, VLSI layout, and perhaps most famously, public key cryptography. In programming contests, the problem sometimes shows up in the form of children picking sides in a ball game so that the game is fair.



The Bounded Knapsack Problem - Instead of N items, you are given M types of items, each type having a bounded quantity.



The Unbounded Knapsack Problem - You have an unbounded quantity of each item type, instead of a bounded quantity.



The Subset-Sum Problem - The same as 0/1 knapsack if profit p[i] equals the weight w[i].



The Change-Making Problem - You are given a target value V and you need to make change for it using the smallest amount coins. The coins have some bounded number of denominations but an unbounded number of available coins in each denomination. This is the same as the unbounded knapsack problem except all the profits are 1 (however, notice that we want to reduce the number of coins, so we want to minimize this profit. some textbooks use a negative value, instead, in order to fit it under the exact same formulation as the knapsack problem.).

You can formulate this recursively this way:
Let c[j] be the optimal number of coins to make value j.
Let m[i] be the list of denominations
Then you can write the following recursive relation:

c[j] =
\begin{cases}
0 & \mbox{ if } j =0\\
1+ \displaystyle\min_i \lbrace c[j-m_i] \rbrace \mbox{ where }  m_i < j & \mbox{ otherwise } \\}
\end{cases}


The Multiple Knapsack Problem - The 0/1 knapsack problem but you are given multiple knapsacks of different sizes. The capacity constraint must be met for all of the knapsacks.



The Bin-Packing Problem - You have some number of equally sized bins. You need to pack the items into bins so that the number of bins used is as small as possible.
Computer Science @ George Mason University