I feel, Knapsack problem is one of the most interesting puzzle to solve. Given a set of items, each with a weight and a value, Knapsack puzzle asks us to determine the number of each item to include in a collection so that the total weight is less than a given limit and the total value is as large as possible. Imagine you in a plane, which is about to crash if certain quantity of goods is not trowed away from flight. Certainly, your program needs to be as quick as possible, otherwise, flight might crash before your program gives you the output. I am sure, you would strive to get the very optimal algorithm, after all life matters more than the goods.. 🙂
There are 2 variations of Knapsack’s problem,
1. 0/1 Knapsack problem – Which restricts the number of items to be included in Knapsack to either 0 or 1.
2. Unbounded Knapsack problem – There is no limit on number of items that could be included in Knapsack.
This section, I will discuss about the solving unbounded Knapsack problem with Dynamic programming approach.
In a dynamic programming solution to the knapsack problem, we calculate the best combination for all Knapsack sizes up to M (Knapsack capacity). Also, let us assume we have N items. It turns out that we can perform this calculation very efficiently by doing things in an appropriate order, as in the following program:
for j:=l to N do
begin
for i:=l to M do
if i-size[j]>=O then
if cost[i]<(cost[i-size[j]]+val[j])
begin
cost[i]:=cost[i-size[j]]+val[j];
best[i] :=j
end ;
end ;
In this program, cost[i] is the highest value that can be achieved with a knapsack of capacity i and best [i] is the last item that was added to achieve that maximum (this is used to recover the contents of the knapsack, as described below). First, we calculate the best that we can do for all knapsack sizes when only items of type A are taken, then we calculate the best that we can do when only A’s and B’s are taken, etc. The solution reduces to a simple calculation for cost [i]. Suppose an item j is chosen for the knapsack: then the best value that could be achieved for the total would be val[j] (for the item) plus cost [i-size(j)] (to fill up the rest of the knapsack). If this value exceeds the best value that can be achieved without an item j, then we update cost [i] and best[i]; otherwise we leave them alone.
For instance, consider the items of following sizes and values,
name A B C D E
size 3 4 7 8 9
value 4 5 10 11 13
The following table traces the comptation for our example. The first pair of lines shows the best that can be done (the contents of the cost and best arrays) with only A’s, the second pair of lines shows the best that can be done with only A’s and B’s, etc.:
1 2 3 4 5 6 7 8 9 1011121314151617
0 0 4 4 4 8 8 8 12 12 12 16 16 16 202020
A A A A A A A A A A A A A A A
0 0 4 5 5 8 9 10 12 13 14 16 17 18 20 21 22
A B B A B B A B B A B B A B B
0 0 4 5 5 8 10 10 12 14 15 16 18 20 20 22 24
A B B A C B A C C A C C A C C
0 0 4 5 5 8 10 11 12 14 15 16 18 20 21 22 24
A B B A C D A C C A C C D C C
0 0 4 5 5 8 10 11 13 14 15 17 18 20 21 23 24
A B B A C D E C C E C C D E
Here is a final note on complexity of this algorithm. It is obvious from inspection of the code that the running time of this algorithm is proportional to NM. Thus, it will be fine if M is not large, but could become unacceptable for large capacities.
C++ implementation of Knapsack problem can be found here.
References:
[A] Algorithms – By Robert Sedgewick
[B] http://en.wikipedia.org/wiki/Knapsack_problem.
0xC0FFEE 