Home > Applied Algorithms, Greedy > The US Pizza Knapsack problem (not 1/0)

The US Pizza Knapsack problem (not 1/0)

Problem Statement: US Pizza gives you a bowl that can hold 100 gms of salad. You have different salad items each having its own Nutritional Value (NV) and availability. You are supposed to find the way one should fill his bowl so that he gets maximum nutrition. They need not take all of the available quantity. Taking a fraction of the salad item is allowed.

Items          Nutrition Value per Gram         Available

Noodle      10                                                           100 gm

Soyabean  30                                                             15 gm

Macroni     5                                                            100 gm

Fruits         40                                                             10 gm

(This problem is being posted to demonstrate what greedy algorithms are. I am sure anyone would have been able to solve this by themselves)

All you need to do here is start with the item that provides the highest nutrition/gram and take the maximum available quantity unless the bowl is full. If after this, the bowl still has space, you take the item with the second highest nutrition/gram value. And so on. 

I am sure you get the idea. For the above example, you would take 10 gm of Fruits (Full = 10, Remaining = 90), 15 gm of Soyabean (Full = 25, Remaining = 75), and to fill up the rest, with 75 gm of Noodles (Full = 100, Remaining = 0). In this way of selection, you get the maximum nutritional value, 1600 (10*40 + 15*30 + 75*10).

So that is what we call a greedy algorithm. Forming the best solution as you go on. 🙂

Advertisements
  1. November 8, 2011 at 11:35 pm

    Pizza salad Hmmm i heard of salad with your pizza but pizza salad interesting Las Vegas Pizza

  1. November 22, 2011 at 2:53 pm

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: