TIL: The greedy algorithm

TIL: The greedy algorithm

Today I Learned about the Greedy Algorithm, which can be used to calculate the minimum elements required from a list that will sum up to a number.

For example:

# An integer
S = 11
# A list of integers
V = [1,2,5]

"""
Write a function to determine the minimum number of elements in list V that can be summed up to S
"""
def minElement(S, V, E=0):
  # V.sort()
  # Edge case where there can only be one element
  if S == 0: return 0
  if S < 1: return E
  E+=1
  return minElement(S-V[-1], V, E)

print(minElement(S, V))

(Note that this is Python)

The code above will output 3.

Here’s a detailed explanation of how the code works:

  1. First, the variables S and V are passed in to the function which is called in the last line. (In this example, S is 11 and V is [1,2,5])
  2. Next, the variable S specified is checked if the number is 0. This is an edge case as there can’t be any number of elements that can form 0. (In this case, this zero check is skipped)
  3. Next, the variable S specified is checked if

About Edric Chan

(site owner)

A 16-year-old tech enthusiast since getting his first MacBook Pro 2015 in the year-end of 2015. When he's not at school, he usually works on small programming projects or reads technology-related books. He currently studies at School of Science & Technology, Singapore and will graduate in 2019 to pursue his post-secondary life.

Share "TIL: The greedy algorithm"

Successfully copied to the clipboard!
An error occurred while attempting to copy to the clipboard
An update is available!