In the past week, I have traveled across 4 major pilgrimage centers and of course accumulated lots of brownie points for no stupid comments on the deities. I have decided to add more content to my site, mostly to make it humorous etc.
Right, I’ve had bloody little opportunity to further my education and I could only manage to read about greedy algorithms (I actually went to greedy algorithms after reading about the Traveling Salesman Problem that Scott Aaronson seemed to have used to write a game in high school).
Greedy algorithms operate by picking the extremum to proceed towards the solution without any regard for what might happen at a later stage of the solution.
I then decided to implement a few greedy algorithms then.
The Number of Coins While Making Change:
The Indian currency is the Rupee and 1 Rupee equals 100 Paise. The coins in circulation are:
- 25 paise (gets you nothing)
- 50 paise (gets you nothing)
- 1 Rupee (gets you enough gum to chew for an hour)
- 2 Rupees (gets you enough gum to chew for 2 hours)
- 5 Rupees (gets you enough gum for an entire day)
So, here is an recursive implementation of this problem:
change.sort()
change.reverse()
give = []
def findMax(amount):
if amount < min(change):
return give
else:
for coin in change:
if coin <= amount:
give.append(coin)
amount -= coin
return findMax(amount)
else:
continue
test_cases = [2500, 7200, 1200, 550, 650, 750, 850]
for amount in test_cases:
print findMax(amount)
give = []
The output:
vvs rao@vvsrao-PC /cygdrive/c/Users/vvs rao/scripts $ python greedy_change.py [500, 500, 500, 500, 500] [500, 500, 500, 500, 500, 500, 500, 500, 500, 500, 500, 500, 500, 500, 200] [500, 500, 200] [500, 50] [500, 100, 50] [500, 200, 50] [500, 200, 100, 50]
When this excessive journeying ends, I will write a few more posts. Goodbye till then
