☰
×

Greedy Algorithms in Python

Chapters

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.

Image 280

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

Image 281

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

Activity Selection

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}

Image 283

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.

Image 284

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.