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

Mouse cursor not visible in Xoo emulator in Karmic (Ubuntu 9.10).

I am a fan Ubuntu Linux, and usually try every new version of Ubuntu as and when it gets released. Till very recently I had Ubuntu 8.04 (Hardy) installed at my office workstation, but I thought lets give a try to Karmic. (Un)Fortunately, my Hardy got screwed up while doing some experiments with it, and now I had a valid reason to reinstall/upgrade of my OS, and so Karmic got installed. 🙂

Everything went well with Karmic, but mouse cursor wasn’t visible in Xoo emulator with Xnest/Xephyr. Xoo is a GTK2 based graphical wrapper around a ‘Windowed’ X Server. The X server is typically Xnest, the nested X server, or Xephyr. It is intended for embedded developers that want to simulate a target device (with an accurate display size, working hardware buttons, etc) on a desktop machine. Emulator used start with following error message, but mouse wasn’t visible at all!!!.


/usr/share/fonts/X11/cyrillic, removing from list!
unrecognised device identifier!
(EE) config/hal: NewInputDeviceRequest failed
unrecognised device identifier!
(EE) config/hal: NewInputDeviceRequest failed
unrecognised device identifier!

Did lot of circus to resolve this error, searched in net, found some some similar topics (like meamo developers), but none of the posts resolved my error.

Finally, found out though some web sources that, Karmic doesn’t have Xnest support, but instead of Xephyr need to be used in Karmic. By default, Xoo starts Xephyr server, but to get host cursor, one need to start xoo with following argument,


xoo -xo -host-cursor

Basically, I just had to pass -host-cursor as argument to Xserver through Xoo.

Uff.. Kind off wasted a day trying to find this single line solution. Hence, thought of sharing this info with all.

Create your own SVN repository for Free with Google.

  • Do you write lot of code?
  • Do you create a lot of revisions of code which are hard to manage by yourself?
  • Do you wish to host your own project online and ask your friends to contribute it?

    Well, if the answer is ‘Yes’ for above, then you should try online project hosting with Google code. Its simple, easy to use and has got tremendous capabilities built in it. Refer Project hosting with Google code for more details.

    I created a test project called ‘Knapsack‘ in Google code, approach I followed was,
    1. I used to SVN as versioning tool.
    2. Followed the procedure mentioned here to check out the initial empty code.
    3. Did svn add to add KnapSack.cpp file to SVN repository.
    4. Check’ed in the code. Thats it!!

    Other interesting options which Google code includes are allowing many people to contribute to your project, getting email notifications upon check-in etc. Having said, now you could start contributing to my KnapSack project.. 🙂

    Bottom line, Google Rocks!! And so is Open Source!!

  • Hello World!

    Being a computer science engineer and a programmer, first post I could think of is “Hello world!”, and here is my “Hello world!”.

    
    void main()
    {
        printf("Hello World!");
    }
    
    

    I’ll try to write up some useful technical stuffs in this blog. Stay tuned!.