Python Algorithm: Pt. 12: GREEDY >:D

Why hello there.

…

…

…

…

…

…

…

…

Wait. Why are you still here?

…

…

…

…

Greedy for more words?

…

…

…

…

I guess so. Well, that is today’s subject: the greedy algorithm.

Seriously though, I have no idea why I am writing these posts. No-one is going to look at my medium page and be like: Woah, this is unique! Eh. Whatever.

What does the greedy algorithm do, you might ask? Well, as the name suggests, greedy people often use it to get the most out of their time. Now let’s give an example.

Derp-kai is hungry. Currently, he needs to eat food to fill his 15 hunger points.

Hunger points: 15

What is our goal here? To make the hunger points go down to 0. To achieve that, Derp-kai needs to eat food that reduces a certain amount of hunger points.

The store has:

Cheeseburger — 5 hunger points — 10 gp

Chicken leg — 3 hunger points — 3 gp

Ice cream — 2 hunger points — 10gp

Derp-sandwich — 10 hunger points — 18gp

Derp-kai felt his mouth water as he reached into his purse and — oh god. I TOLD YOU NOT TO BUY THAT USELESS MAGIC: THE GATHERING BOOSTER BOX! Derp-kai took out his python staff. The problem now is not that Derp-kai has a certain amount of gp, and you can only spend that much to satisfy his hunger. No, he can majick gp into existence with the help of his staff. Economy breaking? Sure. But energy-consuming? Very. So let’s now pretend his gp count is infinite, because he could just use a python spell to gett it. But it costs him energy. He wants to spend as little as possible of his energy. In other words, spend as little as possible gp.

Now is the time to do a algorithm spell to determine the least costly meal!

…

…

…

Actually, never mind. Derp-kai can make food with spells too.

But now you know what we are looking for with the greedy algorithm.

Here are two examples:

1. Class time!

Here, we are trying to fit as much classes as possible in our time.

def greedy(course):
length = len(course)
course_list=[]
course_list.append(course[0])
course_end_time = course_list[0][1][1]
for i in range(1, length):
if course[i][1][0] >= course_end_time:
course_list.append(course[i])
course_end_time = course[i][1][1]
return course_list
course = {
'Biology':(12, 13),
'English':(9, 11),
'Math':(8, 10),
'IT':(10, 12),
'Physics':(11,13),
}
cs = sorted(course.items(), key=lambda item:item[1][1])
print('IDK')
print('Class', '    Starting time', 'FINISH CLASS!')
for i in range(len(cs)):
print("{0}{1:7d}:00{2:8d}:00".format(cs[i][0],cs[i][1][0],cs[i][1][1]))
s=greedy(cs)
print("IDK")
print("Class", "   Starting time", "FINISH CLASS!")
for i in range(len(s)):
print("{0}{1:7d}:00{2:8d}:00".format(s[i][0],s[i][1][0],s[i][1][1]))

Basically, we have two parts in this algorithm. First we determine how long a class is, then we put in the format how it is going to run.

2. Shopping!

Now, now, Derp-kai wants some new items in his inventory! He needs to spend as little gp as possible on them.

def greedy(things):
length = len(things)
things_list = []
things_list.append(things[length-1])
weights = things[length-1][1][1]
for i in range(length-1, -1, -1):
if things[i][1][1] + weights <= max_weight:
things_list.append(things[i])
weights += things[i][1][1]
return things_list
things = {'iWatch':(15000, 0,1),
'Asus':(35000, 0,7),
'iPhone':(38000, 0,3),
'Acer':(40000, 0,8),
'Go Pro':(12000, 0,1),
}
max_weight = 1
th = sorted(things.items(), key=lambda item:item[1][0])
print("IDK")
print('Product', '                Price', 'Weight')
for i in range(len(th)):
print("{0:8s}{1:10d}{2:10.2f}".format(th[i][0],th[i][1][0],th[i][1][1]))
t = greedy(th)
print("IDK")
print("Product", "                            Price", "Weight")
for i in range(len(t)):
print("{0:8s}{1:10d}{2:10.2f}".format(t[i][0],t[i][1][0],t[i][1][1]))

Notice how we defined everything’s cost FIRST.

And that concludes today’s Python lesson!

CLAP FOR ME!! I AM GREEDY!!! MUAHAHAHA! GIMME CLAPS!! MUAHAHAHAHAHA-

Ow. Laughing too hard hurts.

derp.