Greedy algorithms make locally optimal choices at each step with the hope of finding a global optimum. They are simple and efficient but don't always yield the best solution for all problems.
Greedy algorithms are ideal for problems where:
Given a set of activities with 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.
Generate random activities and click "Solve Greedily" to see the algorithm in action.
The greedy approach for activity selection:
function activitySelection(activities):
// Sort activities by finish time
sort activities by finish time
// Select first activity
select first activity
lastFinishTime = finish time of first activity
// Consider remaining activities
for each activity in remaining activities:
if start time of activity ≥ lastFinishTime:
select this activity
lastFinishTime = finish time of this activity
return selected activities
O(n log n) - Dominated by the sorting step
O(n) - To store the activities
Given a set of coin denominations and a target amount, find the minimum number of coins needed to make up that amount. The greedy approach works optimally for some coin systems (like US coins) but not for all possible coin systems.
Select a coin system and amount, then click "Solve Greedily" to see the algorithm in action.
The greedy approach for coin change:
function coinChange(coins, amount):
// Sort coins in descending order
sort coins in descending order
result = []
remaining = amount
for each coin in coins:
// Use as many of this coin as possible
while remaining >= coin:
add coin to result
remaining = remaining - coin
return result
O(amount) - In the worst case, we might need to use all 1-value coins
O(amount) - To store the coins used
The greedy approach works optimally for canonical coin systems where each coin is at least twice the value of the next smaller coin.
Example: US coins (1, 5, 10, 25)
For some coin systems, the greedy approach doesn't yield the optimal solution.
Example: With coins [1, 3, 4] and amount 6, greedy gives [4, 1, 1] (3 coins) but optimal is [3, 3] (2 coins)
Given a set of items with weights and values, and a knapsack with a maximum capacity, determine the maximum value that can be obtained by taking fractions of items if needed.
Generate random items and set a knapsack capacity, then click "Solve Greedily" to see the algorithm in action.
The greedy approach for fractional knapsack:
function fractionalKnapsack(items, capacity):
// Calculate value-to-weight ratio for each item
for each item in items:
item.ratio = item.value / item.weight
// Sort items by value-to-weight ratio in descending order
sort items by ratio in descending order
totalValue = 0
remainingCapacity = capacity
for each item in items:
if remainingCapacity >= item.weight:
// Take the whole item
take item completely
totalValue += item.value
remainingCapacity -= item.weight
else:
// Take a fraction of the item
fraction = remainingCapacity / item.weight
totalValue += item.value * fraction
remainingCapacity = 0
break
return totalValue
O(n log n) - Dominated by the sorting step
O(n) - To store the items
In the fractional knapsack problem, we can take fractions of items, making it solvable with a greedy approach.
In contrast, the 0/1 knapsack problem (where we must take items whole or not at all) requires dynamic programming for an optimal solution.
Fractional knapsack models resource allocation problems where resources are divisible:
Greedy algorithms are most effective when: