## 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
• Input:
• Some set of N items. Each item i is associated with weight w[i] and profit p[i].
• A maximum weight W.
• Output:
• The maximum profit sum P possible without exceeding the weight capacity W.
• A subset of the items which maximizes the profit sum without exceeding the weight capacity W.
• The subset is usually given by a bit vector s of size N where s[i]=1 represents that item i is included in the knapsack. (Hence the name 0/1 Knapsack)

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;  // no items left
for (j = 0; j <= W; j++) P[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.
• Input:
• A set of integers, S.
• Output:
• For each integer i in S, a 0 or 1 indicating which side of the partition it is on.

The Bounded Knapsack Problem - Instead of N items, you are given M types of items, each type having a bounded quantity.
• Input:
• Some set of M types of items, each item type m having bounded quantity q[m] and associated with weight w[m] and profit p[m]
• A maximum weight W.
• Output:
• The amount of each type of item should be included in the knapsack to maximize profit sum without exceeding weight capacity W and subject to the bounded quantity for each item type.

The Unbounded Knapsack Problem - You have an unbounded quantity of each item type, instead of a bounded quantity.
• Input:
• Some set of M types of items, each item type m having unbounded quantity and associated with weight w[m] and profit p[m]
• A maximum weight W.
• Output
• The amount of each type of item should be included in the knapsack to maximize profit sum without exceeding weight capacity W.

The Subset-Sum Problem - The same as 0/1 knapsack if profit p[i] equals the weight w[i].
• Input:
• Some set of N numbers.
• A target value W
• Output:
• A subset of the N numbers so that the sum is as large as possible without exceeding W.

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.).
• Input:
• Some set of M denominations.
• A target value V
• Output:
• The amount of each denomination that should be included in the knapsack to maximize profit sum without exceeding weight capacity W.

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: 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.
• Input:
• Some set of N items. Each item i is associated with weight w[i] and profit p[i].
• Some set of knapsacks W with max size of knapsack k given by W[k]
• Output:
• A subset S of the items and which knapsack they are in.
• For item i, S[i] will indicate the knapsack the item is in so that the profit is maximized without exceeding the capacity of any knapsack.

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.
• Input:
• The number of bins N.
• The size of the bins K.
• Output:
• For each item i, S[i] represents the bin that the item is in so that the number of bins used is minimized.