November 15, 2015

Greedy Technique

technology

Hi all! Its been a while since I last wrote. I plan to write down anything I understand about greedy technique, like last time I did for hashing. As the name implies, this technique is..greedy. Like humans. We make choice which will provide us the best result as soon as possible. This technique is exactly the same. We make choices seeing the local choices and not worrying about the future. This technique is generally used in optimization problem, finding minimum or maximum related problems. I am not aware of any formal definition as such. Regardless the best way to open up my mind regarding this, would be to begin explaining an example. If you are following me from my first post, I had noted, I plan to write almost all my codes in python. The logic would be the same, so implementing it in some other language would not be a big deal.

I plan to solve this problem. Click to read the question.

Mark and Jane are very happy after having their first child. Their son loves toys, so Mark wants to buy some. There are a number of different toys lying in front of him, tagged with their prices. Mark has only a certain amount to spend, and he wants to maximize the number of toys he buys with this money. Given a list of toy prices and an amount to spend, determine the maximum number of gifts he can buy.

Note Each toy can be purchased only once.

Example

prices = [1, 2, 3, 4] k = 7

The budget is 7 units of currency. He can buy items that cost [1, 2, 3] for 6, or [3, 4] for 7 units. The maximum is 3 items.

Function Description

Complete the function maximumToys in the editor below.

maximumToys has the following parameter(s):

int prices[n]: the toy prices
int k: Mark’s budget

Returns

int: the maximum number of toys

Input Format

The first line contains two integers, n and k, the number of priced toys and the amount Mark has to spend. The next line contains n space-separated integers prices[i]

Constraints

1 ≤ n ≤ 10⁵ 1 ≤ k ≤ 10⁹ 1 ≤ prices[i] ≤ 10⁹ A toy can’t be bought multiple times.

Sample Input

7 50
1 12 5 111 200 1000 10

Sample Output

Explanation

He can buy only 4 toys at most. These toys have the following prices: 1, 12, 5, 10.

In short words we have to find the maximum amount of toys we can buy from an array of prices N with K money at hand. If you give it a thought, the solution you will arrive at is to buy the minimum price of toys till it doesn’t exceed K. That is exactly what greedy is(and us, humans). Since we consider every toy to be of equal ‘quality’ and are concerned with maximum quantity, the most intuitive way of thinking would be to buy toys with minimum price tags. We are already done with the logic of our problem! This can be easily solved by first sorting the price list with ascending order and keeping the track of the total purchase. Once it becomes greater than K we know that we have reached our limit. Here is a simple python code to implement this.

n is the size of the list of prices

k is the money we have

toys is price list

def max_toys(n, k, toys):
    toys.sort() #ascending order
    total = 0
    count = 0

    for x in xrange(n):

         total = toys[x] + total

         if total >= k:
             return count

         else:
             count += 1

    return count     #if we have money to buy all

This was a very simple example to show how greedy technique works. In some problems it will be hard to consider if greedy would lead to an optimal solution. It can also be said in another way that, understanding greedy algorithms and to implement them is one of the easiest, it provides easy solution to complex problems. At the same time, to prove its correctness is hard. You might find a greedy solution and you won’t be sure that it will give you the correct answer. But as they say, practice makes perfect. Practice problems and you will be confident on your approach to greediness! 🙂