Greedy techniques
Greedy algorithm
• A greedy algorithm, as the name
suggests, always makes the choice that seems
to be the best at that moment
Some greedy techniques
• fractional knapsack
• Activity Selection Problem
• Minimum Swaps for Bracket Balancing
• Policemen catch thieves
• Assign Mice to Holes
• Kruskal’s Minimum Spanning Tree (MST)
• Prim’s Minimum Spanning Tree
• Dijkstra’s Shortest Path
fractional knapsack
• Given the weights and profits of N items, in the form
of {profit, weight} put these items in a knapsack of
capacity W to get the maximum total profit in the knapsack.
In Fractional Knapsack, we can break items for maximizing
the total value of the knapsack.
• Input: arr[] = {{60, 10}, {100, 20}, {120, 30}}, W = 50
Output: 240
Explanation: By taking items of weight 10 and 20 kg and 2/3
fraction of 30 kg.
Hence total price will be 60+100+(2/3)(120) = 240
Activity Selection Problem
• You are given n activities with their start and finish times.
Select the maximum number of activities that can be
performed by a single person, assuming that a person can
only work on a single activity at a time.
• Input: start[] = {1, 3, 0, 5, 8, 5}, finish[] = {2, 4, 6, 7, 9, 9};
Output: 0 1 3 4
Explanation: A person can perform at most four activities.
The
maximum set of activities that can be executed
is {0, 1, 3, 4} [ These are indexes in start[] and finish[]
Minimum Swaps for Bracket Balancing
• You are given a string of 2N characters consisting of N ‘[‘ brackets and N ‘]’
brackets. A string is considered balanced if it can be represented in the
form S2[S1] where S1 and S2 are balanced strings. We can make an
unbalanced string balanced by swapping adjacent characters. Calculate
the minimum number of swaps necessary to make a string balanced.
• Input : []][][
Output : 2
First swap: Position 3 and 4
[][]][
Second swap: Position 5 and 6
[][][]
Policemen catch thieves
• Given an array of size n that has the following
specifications:
• Each element in the array contains either a
policeman or a thief.
• Each policeman can catch only one thief.
• A policeman cannot catch a thief who is more
than K units away from the policeman.
We need to find the maximum number of thieves
that can be caught.
Example
Input : arr[] = {'P', 'T', 'T', 'P', 'T'}, k = 1.
Output : 2
Here maximum 2 thieves can be caught, first
policeman catches first thief and second police-
man can catch either second or third thief.
Assign Mice to Holes
• There are N Mice and N holes are placed in a straight line.
Each hole can accommodate only 1 mouse. A mouse can stay
at his position, move one step right from x to x + 1, or move
one step left from x to x -1. Any of these moves consumes 1
minute. Assign mice to holes so that the time when the last
mouse gets inside a hole is minimized.
Example
Input :
positions of mice are: 4 -4 2
positions of holes are: 4 0 5
Output : 4
Assign mouse at position x = 4 to hole at position x = 4 : Time taken is 0
minutes.
Assign mouse at position x=-4 to hole at position x = 0 : Time taken is 4
minutes.
Assign mouse at position x=2 to hole at position x = 5 : Time taken is 3
minutes.
After 4 minutes all of the mice are in the holes. Since, there is no
combination possible where the last mouse's time is less than 4, answer
= 4.
problem
