Archive

Posts Tagged ‘Greedy’

Stable Marriage Problem

Please note before diving in: This is an algorithmic problem. If you land at this page looking for solution to something different, please visit a marriage counselor. 😛

Poor jokes apart, this one is another famous problem of the computer science domain. Here is how the problem statement goes: (source: Wikipedia)

Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are “stable”.

So basically you have to pair people in such a way that they have no better choice. You are given the preference list of each of the n men and n women and are supposed to give the perfect pairing. Now with no other conditions imposed, you can treat this problem as a simple greedy problem. Here is what your algorithm should do:

The algorithm will work in iterations.

For the first time, each unengaged man proposed to the woman he prefers the most (i.e., woman highest on his priority list). All the women would consider their proposals and select the proposal from the man who is higher than others on her list of preferences. They are now tentatively engaged.

Now in every iteration from now on, each unengaged man will propose to the woman who is next on his list of preferences. The women will compare all the proposals they are currently getting along with the one whom they are tentatively engaged to (if any). They will again select the proposal of the man who is highest on their list of preferences.

This process stops when all men are engaged after an iteration.

This greedy method was simple to understand and hopefully you would have got it by now. This is known as the Gale-Shapley algorithm. If anyone has any trouble in figuring it out, check out the gif animation below to see a sample case.

Brilliant! So you are now equipped with another algorithm to tackle your day-to-day marital, friendship and roommate related problems. 🙂

Have fun!

The US Pizza Knapsack problem (not 1/0)

October 25, 2011 2 comments

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

The circularly-arranged petrol pump problem.

October 15, 2011 3 comments

Problem Statement: You are given n petrol pumps arranged in a circle. There is a certain quantity of petrol that is available at each pump. And you are given the amount of petrol required to reach from each station to the next. You have to find out the petrol pump starting at which you can go around and come back to that particular petrol pump.

Can you think up of a quick method of solving this? I can do it in O(n). Let me explain the method. Take any petrol pump randomly as your START. Take the next pump as END. Now you have an available quantity of petrol at START. See if this quantity is enough to reach END, i.e., is available quantity greater than or equal to required quantity. If yes, add the quantity of petrol available at END to your available quantity and then move END one pump ahead. Now perform the same check between available and required. In case available<required, move your START one pump back, adding the quantity of that pump to your available and adding the required from your new START to the old one to your required. Following this method, you’ll finally converge at a pump (i.e., START=END). This is your required petrol pump. 🙂

Since there is no problem in coding this, I’ll just show an example and get done with this.

In this image (if you can’t view the image, you are probably not viewing this post on my blog), each petrol pump has an available quantity of petrol and the required quantity to reach the next pump. Let us start with the solution by randomly picking START as pump C. There, END is pump D.

available = 3, required = 10

Since available < required, move START back to B.

Now, available = 5+3, required = 10+6

Still available < required, move START back to A.

Now available = 5+3+9, required = 10+6+2

Still available < required, move START back to D.

available = 5+3+9+6, required = 10+6+2+5

Now, available = required and START=END. Hence, the required pump is pump D. You can repeat the process starting at any pump and you would get the right answer. 😉

With that, we come to the end of a lengthy explanation of the problem. But I hope all of you understood it. 🙂

%d bloggers like this: