Skip to content

Instantly share code, notes, and snippets.

@iamjosephmj
Created July 14, 2020 23:30
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save iamjosephmj/8b3b070c54012676fc5d70c7eb9b421a to your computer and use it in GitHub Desktop.
class Greedy:
'''
The constructor takes to parameters
:denominations -> ($20,$10,$5..etc)
:target -> amount to be given to Joseph
'''
def __init__(self,deominations,target):
self.denominations = deominations
self.target = target
def start_greedy_algorithm(self):
dm = list() #Ashels starts with no denominations.
amt = 0 # sum of the denominations to be given to joseph
#Other variables
deno_index = 0
while(amt <= self.target):
'''
using while loop because we do have an indefenite number of steps
'''
if amt + self.denominations[deno_index] <= self.target:
amt += self.denominations[deno_index]
dm.append(self.denominations[deno_index])
elif len(self.denominations) > deno_index+1:
deno_index+=1
else:
break
return dm
print(Greedy([20,10,5],45).start_greedy_algorithm())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment