Greedy Algorithms Explained

Welcome to another video! In this video, I am going to cover greedy algorithms. Specifically, what a greedy algorithm is and how to create a greedy algorithm. I'll also show you some examples of greedy algorithms.

📄 Resources 📄

⭐️ Timestamps ⭐️
00:00 | Overview
01:28 | What Are Greedy Algorithms?
04:02 | Greedy Algorithm Properties
05:42 | Fractional Knapsack Problem
15:03 | Knapsack Problem

◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️
💰 Courses & Merch 💰

🔗 Social Medias 🔗

🎬 My YouTube Gear 🎬

💸 Donations 💸
◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️

⭐️ Tags ⭐️
- Tech With Tim
- Greedy Algorithm
- Examples
- Knapsack Problem
- Fractional Knapsack Problem
- Algoexpert

⭐️ Hashtags ⭐️
#TechWithTim #GreedyAlgorithms

[evgizr]

transforming the 0 into 1 was too greedy :)

[Rebeljah]

I already had the answer to optimal solution but only because this is EXACTLY what you do in your head when you are comparing prices at a grocery store. Maximizing the value/size ratio to stay within a certain limit (your grocery budget).

[sumukhjagirdar]

Hi Tim. Today is my birthday. I love your content

Tim, please more videos like this. 20-30 videos of Greedy algorithms then 20-30 videos of Dynamic programming, then Divide and Conquer - this is the real programming: Django, Flask, React everyone can learn fast, but Algorithms are more important.

[futhedude]

this is just explain for "Fractional Knapsach Problem" solved by "Greedy Algorithms", there are many more Problems we can use "Greedy" to resolve.
but this clip is good at explaining so well done.

[ofiryaffe]

Nice video, also a good example because I actually understood on my own the greedy algorithm of the fractional knapsack problem. Keep making videos about algorithms !

[whyisknighttaken]

why isn't it 4, 3, 2, 0 for a sum of 9? at 3:12

[ashleydean]

Hello .
I am new to this topic - however with your explanation and some maths background this is easy topic to understand.
Excellent explanation.
Tim you are doing a superb job- keep it up.

[khimleshgajuddhur]

3:12
you said: we select 0 but how can you get 1 then 😕😁😢

[Raghav]

Hi Tim can we expect more questions on algoexpert?

[dominator]

You always upload a video on the topic I wanna learn haha. (btw idk if you knew this but fresca in arabic means a type of sweet snacks :D )

[codeaperture]

We're greedy more algorithms in future 🔥

[yvanbrunel]

Thank you very much!!
I'll try implementing this in a c++ program.

[rl]

Tons of thanks.. I hope you will continue to more algorithms

[sunitmody]

This is really useful Tim, but you might want to be slightly more careful with the numbers you say and write on the screen lol. A couple of times you misspoke or mis-wrote.

[pedrorequio]

Do a series on Metaheuristics, the video simplifies alot what I know is a very difficult subject, not all problems are small enough to solve like this in code or have simple heuristics to solve. I am interested in more videos on this kind of algorithms of optimization.

[cuteflygon]

funny thing is 18 is also the optimal solution for non-fractional units, isn't it? A lucky example :p

[Cookie-mvhg]

I'm all in for an algorithm series from Tim ! I'll even pay for that!!

[aravindhang]

I would like to see contents on dynamic programming too tim

[korsik]

def algorithm(items, capacity):
ratio = sorted([(size, value, value / size)
for size, value in items], key=lambda tup: tup[2], reverse=True)
total_size = total_value = 0
for size, value, _ in ratio:
new_size = total_size + size
if new_size > capacity:
break
total_size = new_size
total_value += value
else:
return total_value
return total_value + (capacity - total_size) / size * value


items = ((22, 19), (10, 9), (9, 9), (7, 6))
capacity = 25

print(algorithm(items, capacity))