bd
Greedy Algorithms
A greedy algorithm always makes the choice that looks best at this moment.
Practice problems:
1. Fractional knapsack
Sample input Sample output
W
n
item, value, weight
…
15 Taking gold-dust 8.0 kg -- 2000.0 taka
4 Taking silver-dust 4.0 kg -- 300.0 taka
silver-dust 300 4
Taking sugar 3.0 kg -- 26.7 taka
gold-dust 2000 8
salt 80 10
sugar 89 10 Total profit 2326.7 taka
25 Taking gold-dust 8.0 kg -- 2000.0 taka
4 Taking silver-dust 4.0 kg -- 300.0 taka
silver-dust 300 4
Taking sugar 10.0 kg -- 89.0 taka
gold-dust 2000 8
salt 80 10 Taking salt 3.0 kg -- 24.0 taka
sugar 89 10
Total profit 2413.0 taka
2. Activity Selection Problem
Greedy algorithms for this problem:
• Sort by start time
• Sort by finish time (this one gives the optimal answer)
• Sort by interval
The following two pseudo codes assume that the activities are sorted according to finish time.
[email protected]
Recursive version:
For-loop version:
Activity selection in different scenario: Version 1
Suppose you are a coder. You write code for money and charge each customer the same
amount, M, irrespective of how many hours it takes to write the code. Your customers have sent
you n coding requests for tomorrow. Each coding request contains the customer id (𝒄𝒊 ), the start
time (𝒔𝒊 ) and the duration (𝒅𝒊 ) of the coding task. Write a code to maximize your income
tomorrow. Note that you can only write code for one customer at a time.
Sample input Sample output
M
N
𝑐1 , 𝑠1 , 𝑑1
…
𝑐𝑛 , 𝑠𝑛 , 𝑑𝑛
10 Profit: 3x10=30
4 Chosen tasks:
a 2 8
b
b 3 4
d 8 1 c
c 7 1 d
Activity selection in different scenario: Version 2
Note that you need X hour break between two code writing tasks.
[email protected] Sample input Sample output
M, X
N
𝑐1 , 𝑠1 , 𝑑1
…
𝑐𝑛 , 𝑠𝑛 , 𝑑𝑛
10 1 Profit: 2x10=30
4 Chosen tasks:
a28 b
b34 d
d81
c71
3. Maximize your payment
Suppose you are temporarily working as a photoshop editor. You work 10 hours a day from 12:00
PM to 10 PM. Each of your customers sends you a task request for the next day. The task request
contains the payment (p_i), the duration (d_i), and the deadline (dl_i). You must complete a task
within the given deadline to get the payment. Write the following greedy algorithm to maximize
your payment. Note that you can move on to a new task leaving the current task partially
complete, and then come back to it later.
Algorithm:
1. Sort the tasks by descending order of payment per hour.
2. Choose the task with the maximum payment per hour and do it in the last possible hours.
Make that hour occupied.
3. Choose the next maximum paid (payment per hour) task, find the last possible time that is
not occupied, do it at that time and make that hour occupied. If no such time exists, you
cannot do this task.
4. Move to the next maximum profitable task (based on payment per hour) and repeat step 3.
Sample Input Sample Output
c, a
Customer Last time (PM) Time needed (hour) Payment (Tk) 6000
a 4 2 2000
b 1 1 1000
c 1 1 4000
d 2 2 3000
c, a, e
Customer Last time (PM) Time needed (hour) Payment (Tk) 1420
a 2 1 1000
b 1 1 190
c 2 1 270
d 1 1 250
e 3 1 150
[email protected]4. Greedy Coin Change
Consider the problem of making change for N cents using the fewest number of coins. Assume
that each coin’s value is an integer. Write a greedy algorithm to make change consisting of
quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent).
Sample input Sample output
N
173 25 cents --- 6
10 cents --- 2
1 cents --- 3
Total 11 coins
Consider the problem of making change for N cents using the fewest number of coins. Assume
that each coin’s value is an integer. Write a greedy algorithm to make change consisting of coins
𝒄𝟏 , 𝒄𝟐 , … , 𝒄𝒅 .
Sample input Sample output
N
d
𝑐1 , 𝑐2 , … , 𝑐𝑑
173 25 cents --- 6
10 1 25 5 10 cents --- 2
1 cents --- 3
Total 11 coins
5. Determine the smallest set of unit-length closed intervals
Given a set 𝑥1 ≤ 𝑥2 ≤ ⋯ ≤ 𝑥𝑛 of points on the real line, give an algorithm to determine the smallest
set of unit-length closed intervals that contains all of the points. A closed interval includes both its
endpoints; for example, the interval [1: 25; 2: 25] includes all 𝑥𝑖 such that1.25 ≤ 𝑥𝑖 ≤ 2.25.
Sample input Sample output
n
x1, x2, …, xn
6
5.22
6.1
2.2
2.5
3.25
4.8
5
5.22
6.1
2.2
2.5
3.25
[email protected]6. Huffman Encoding
Huffman Decoding
7. More practice problems: https://leetcode.com/tag/greedy/
