Knapsack Problem

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.

Advertisements
Post a comment or leave a trackback: Trackback URL.

Comments

  • PKG  On January 18, 2010 at 10:23 am

    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].

    • nayankk  On January 26, 2010 at 7:43 pm

      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.

  • Gops  On October 7, 2010 at 2:39 pm

    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. <> ;!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: