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.

## Comments

You probably mean “fractional” instead of unbounded- fractional means any fraction between 0 & 1 of an item can go into the knapsack. If this is the case, it’s easy to solve the problem greedily. It’s for the 0-1 case that you need dynamic programming – and this is the hard version of the knapsack.

One more thing.. even if the running time is proportional to NM, it’s still exponential in an important sense (How?). Otherwise,we wouldn’t have the knapsack cipher [ See http://www.quadibloc.com/crypto/pk0504.htm for example].

Nope. As you mentioned “Fractional” means any fraction between 0 & 1 of an item can go into the knapsack. Whereas, in case of Un-bounded Knapsack variant, “one or more” number of each item can go into Knapsack. Hence, we need dynamic programming approach here.

I loved this concept .. when i was pursuing my bachelors in IT ..

What are the top 5 practical applications of this algorithm .. u can think off ??

I thought of ,

1. A store which has ON SALE offers, which has same limitations of Knapsack !

2. Resource Management with billing information for any IT project !

3. Solid Waste Management

4. Shipping consignments with same limitations of Knapsack of ( size & number of items )

5. <

> ;!