A greedy algorithm is a method of solving a problem that chooses the best solution available at the time. It is not concerned about whether the current best outcome will lead to the overall best result.
Even if the previous option was incorrect, a greedy algorithm doesn’t reverse its earlier decisions. It operates in a top-down approach. This algorithm may not produce the best result for all the problems.
Greedy Algorithm works on the following approach:
- It is an algorithm paradigm that builds the solution piece by piece.
- For each step, it offers the piece offering the most immediate benefit.
- It fits perfecty for those algorithms where local optimal solutions lead to global solution.
In the previous articles, we have performed some operations that use the greedy algorithm approach. They are:
In this article, we will look at some more problems utilizing the greedy algorithm approach such as:
- Activity Selection Problem
- Coin Change Problem
- Fractional Knapsack Problem
Activity Selection Problem
We are given N number of activities with their start and finish times. A person can only work on a single activity at a time. According to the problem question, we need to select the maximum number of activities that can be performed by a single person
Implementation of Activity Selection Problem
The Activity Selection Problem makes use of the Greedy Algorithm in the following manner:
- First, sort the activities based on their finish time.
- Select the first activity from the sorted list and print it.
- For all the remaining activities, check whether the start time of the activity is greater or equal to the finish time ofthe previously selevted activity. If so, select this activity and print it.
#Initializing activities with start and finish times
activities = [["A1", 0, 6],
["A2", 3, 4],
["A3", 1, 2],
["A4", 5, 8],
["A5", 5, 7],
["A6", 8, 9]
]
#Function to solve the Activity Selection Problem
def printMaxActivities(activities):
activities.sort(key=lambda x: x[2])
i = 0
firstA = activities[i][0]
print(firstA)
for j in range(len(activities)):
if activities[j][1] > activities[i][2]:
print(activities[j][0])
i = j
printMaxActivities(activities)
Output
Time and Space Complexity
The time complexity for the Activity Selection Problem is O(NlogN) as it takes this much time to sort the unsorted list of activities. The space complexity is O(1) as no additional memory is required.
Coin Change Problem
We are given a number of coins of different denominations and the total amount of money. Find the minimum number of coins that are needed to make up the given amount.
An infinite supply of denominations: {1, 2, 5, 10, 20, 50, 100, 1000}
Implementation of Coin Change Problem
The Coin Change Problem makes use of the Greedy Algorithm in the following manner:
- Find the biggest coin that is less than the given total amount.
- Add the coin to the result and subtract it from the total amount to get the pending amount.
- If the pending amount is zero, print the result.
- Else, repeat the mentioned steps till the pending amount reduces to zero.
#Function to solve the coin change problem
def coinChange(totalNumber, coins):
N = totalNumber
coins.sort()
index = len(coins)-1
while True:
coinValue = coins[index]
if N >= coinValue:
print(coinValue)
N = N - coinValue
if N < coinValue:
index -= 1
if N == 0:
break
coins = [1,2,5,10,20,50,100,1000]
coinChange(122, coins)
#Output
100
20
2
Time and Space Complexity
The time complexity for the Coin Change Problem is O(N) because we iterate through all the elements of the given list of coin denominations. The space complexity is O(1) as no additional memory is required.
Fractional Knapsack Problem
We are given a set of items, each with a weight and a value. Determine the number of each item to include in a collection such that the total weight is less than or equal to a given limit and the total value is as large as possible.
Implementation of Fractional Knapsack Problem
The Fractional Knapsack Problem makes use of the Greedy Algorithm in the following manner:
- Calculate the density for each item. It is defined as the ration of value to weight of the given item.
- Sort the items based on this ratio.
- Select items with the highest ratio sequentially until the space in the collection allows.
- Add the remaining items as much as possible.
#Initializing the Items class with data variables - weight and value
class Item:
def __init__(self, weight, value):
self.weight = weight
self.value = value
self.ratio = value / weight
#Function to solve the Fractional Knapsack Problem
def knapsackMethod(items, capacity):
items.sort(key=lambda x: x.ratio, reverse = True)
usedCapacity = 0
totalValue = 0
for i in items:
if usedCapacity + i.weight <= capacity:
usedCapacity += i.weight
totalValue += i.value
else:
unusedWeight = capacity - usedCapacity
value = i.ratio * unusedWeight
usedCapacity += unusedWeight
totalValue += value
if usedCapacity == capacity:
break
print("Total value obtained: "+str(totalValue))
item1 = Item(20,100)
item2 = Item(30,120)
item3 = Item(10,60)
cList = [item1, item2, item3]
knapsackMethod(cList, 50)
#Output
Total value obtained: 240.0
Time and Space Complexity
The time complexity for the Fractional Knapsack Problem is O(NlogN) as it takes this much time to sort the unsorted list of items based on their calculated ratios. The space complexity is O(1) as no additional memory is required.