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.
💻 AlgoExpert is the coding interview prep platform that I used to ace my Microsoft and Shopify interviews. Check it out and get a discount on the platform using the code "techwithtim" algoexpert.io/techwithtim
📄 Resources 📄
Definitions From: brilliant.org/wiki/greedy-alg...
⭐️ 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 💰
💻 The Fundamentals of Programming w/ Python: tech-with-tim.teachable.com/p...
👕 Merchandise: teespring.com/stores/tech-wit...
🔗 Social Medias 🔗
📸 Instagram: / tech_with_tim
📱 Twitter: / techwithtimm
⭐ Discord: / discord
📝 LinkedIn: / tim-ruscica-82631b179
🌎 Website: techwithtim.net
📂 GitHub: github.com/techwithtim
🔊 Podcast: anchor.fm/tech-with-tim
🎬 My KZbin Gear 🎬
🎥 Main Camera (EOS Canon 90D): amzn.to/3cY23y9
🎥 Secondary Camera (Panasonic Lumix G7): amzn.to/3fl2iEV
📹 Main Lens (EFS 24mm f/2.8): amzn.to/2Yuol5r
🕹 Tripod: amzn.to/3hpSprv
🎤 Main Microphone (Rode NT1): amzn.to/2HrZxXc
🎤 Secondary Microphone (Synco Wireless Lapel System): amzn.to/3e07Swl
🎤 Third Microphone (Rode NTG4+): amzn.to/3oi0v8Z
☀️ Lights: amzn.to/2ApeiXr
⌨ Keyboard (Daskeyboard 4Q): amzn.to/2YpN5vm
🖱 Mouse (Logitech MX Master): amzn.to/2HsmRDN
📸 Webcam (Logitech 1080p Pro): amzn.to/2B2IXcQ
📢 Speaker (Beats Pill): amzn.to/2XYc5ef
🎧 Headphones (Bose Quiet Comfort 35): amzn.to/2MWbl3e
🌞 Lamp (BenQ E-reading Lamp): amzn.to/3e0UCr8
🌞 Secondary Lamp (BenQ Screenbar Plus): amzn.to/30Dtafi
💻 Monitor (BenQ EX2780Q): amzn.to/2HsmUPZ
💻 Monitor (LG Ultrawide 34WN750): amzn.to/3dSD7tS
🎙 Mic Boom Arm (Rode PSA 1): amzn.to/30EZw9m
🎚 Audio Interface (Focusrite Scarlet 4i4): amzn.to/2TjXsih
💸 Donations 💸
💵 One-Time Donations: www.paypal.com/donate?hosted_...
💰 Patreon: / techwithtim
◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️
⭐️ Tags ⭐️
- Tech With Tim
- Greedy Algorithm
- Examples
- Knapsack Problem
- Fractional Knapsack Problem
- Algoexpert
⭐️ Hashtags ⭐️
#TechWithTim #GreedyAlgorithms

[@evgiz0r]

transforming the 0 into 1 was too greedy :)

[@shubhamg9495]

Hahaha

[@Im.justsayin]

😂😂

[@billmaniatis3582]

Xdd😂

[@MahmoudSayed-hg8rb]

is that a mistake tho? I don't get it

[@danagharz90]

😭😭😭😭

[@ofiryaffe8223]

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 !

[@736939]

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.

[@dylanwilliams9860]

Do you realise how much work goes into even a single video? The research and fact checking, development, storyboarding, editing and all the steps I didnt mention mean a 20 minute video for us takes 2-4 days each to make. 20 videos is way way way overkill for just about anything you could want to learn. You would actually want like 3-5 videos on it as thats an hour and a half of lectures, is more than enough to explain a topic, and won't take him a full year to get out.

[@rortox1539]

@@dylanwilliams9860 This. Most people dont realize that they get literal days of work for absolutely free on KZbin

[@736939]

@@dylanwilliams9860 Yes, I realize, but anyone can spend 15-20 minutes for creating video to discuss only one competitive programming problem.

[@dylanwilliams9860]

@@736939 first off, competitive programming is fun. But its full of bad practices that should never be within 300 light-years of production code. Secondly, I just said the videos take days to create and check. Most Vlogs even take several hours worth of takes for big channels. The only time something takes "20 minutes" is in your head or on stream.

[@joshk9328]

Or maybe you could create your own youtube channel and let people upload the content that they want?

[@ashleydean9350]

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.

[@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).

[@radicalpotato666]

The grocery budget is typically a range, so I think the greedy algorithm may be quite helpful.

[@mintlatte1376]

well, in my head I don't have to write a code to make it work, every one walks through the logic and no one shows how on earth I should code all this(

[@sumukhjagirdar5860]

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

[@venkatesanjayaraman2987]

Happy birthday🥳 2 u

[@kiw.]

Happy birthday❤️

[@TechWithTim]

Happy birthday!

[@DewasSquid]

happy birthday! 🥳

[@shemdogga2845]

No one cares it’s your birthday

[@kian180]

Love the content. Fair play to you keep it coming

[@pedrorequio5515]

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.

[@dominator1699]

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 )

[@Jkindelb]

Awesome ty for the explanation! Any chance on going over a flow (vector) field in the future?

[@r125l6]

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

[@yvanbrunel9734]

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

[@whyisknight6taken]

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

[@woolfool]

It also confuses me. Where does the 1 come from?

[@daverobertson8399]

@@shdwshdw-mu6vo If 4 = 4 and 3 = 3, then 0 does not = 1

[@sukhmandersingh4306]

@@shdwshdw-mu6vo no that's not true, 0 and 1 are completely different. Values other than 0 maybe treated as 1 in some cases but i have never seen 0 treated as 1. Tim most likely just made a mistake there.

[@antoine_9667]

it shouldn t he messed up :)

[@samcarter9111]

I'm sure it was a mistake

[@khimleshgajuddhur6892]

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

[@RobertPorterNZ]

Yeh I was thinking the same... max total would be 9?

[@khimleshgajuddhur6892]

@@RobertPorterNZ yes🙄

[@rbrojas2040]

I think it's an error, you should bring down 0, which would make the sum 9, like @Robert Porter said.

[@ananthramvijayaraj4554]

I loved this video. Please continue this algorithms and data structures series

[@Raghav1205]

Hi Tim can we expect more questions on algoexpert?

[@raghaventrarajaram]

Thanks for the help brother.

[@aravindhang1264]

I would like to see contents on dynamic programming too tim

[@futhedude4848]

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.

[@sanduchicu7545]

love how you explain

[@pythonenthusiast9292]

Can we expect a playlist on greedy or DP?

[@CodeWithJoe]

Good video dude, how would you implemnt this algo in python, can you do a practical example

[@judedavis92]

Now this is more like it!! 🔥

[@kietphamhoanganh5641]

thank you so much!

[@evantoomey6712]

Great video. I have this exact problem in Skyrim.

[@codeaperture]

We're greedy more algorithms in future 🔥

[@noobypro4560]

yeaaaaaa boii tim made an algorithm video this gonna be amazing

[@Cookie-mv2hg]

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

[@justins7796]

Algorithm: *Laughs* *in* *Mr* *Krabs*

[@korsik4559]

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))

[@ajaswanth6607]

Why 1 instead 0

[@ajaswanth6607]

1 is not in the array

[@clashgamers4072]

It's a mistake

[@kasyapdharanikota8570]

please more videos like this

[@DaigoMatsuoka]

And what about the code how they look like?

[@PP-tc1zp]

Hi Tim Can You make tutorial about implemate ai to some game(like birds example) in python? It was super.

[@heh2k]

Greedy means the solution is self-similar - it works at smaller scales (subsets) within the same input.

[@ys98110]

??? If you can get fractions of item, why not just select the best value/size item for all? What's the point in just getting one of it? Really don't understand how this derives any optimal solution.

[@shawnbeans7389]

tim when are you doing more podcasts? pls reply

[@demonslayer8502]

Awesome 😎

[@cuteflygon]

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

[@alihusham1560]

I would solve it with recursion just like the coins exchange problem

[@ajaswanth6607]

Expecting more ds and algo

[@vishwakamps]

the handwriting is not so bad man. Its better than mine 😆

[@sunitmody6064]

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.

[@unknownman5296]

please make a algoithm and data structures tutorial

[@billowen3285]

Pretty big topic lol

[@pv9060]

Fun Fact: Texting robots on Mars use python to send images to the earth. It uses request module to communicate with the API on mars.

[@fojifojigurjar2461]

Brother Mico graddy solution please

[@mohitjain4943]

NEED MORE DS AND ALGO!❤❤❤❤

[@phivebee]

The Hamster Kombat problem

[@harshit.chitkara]

Wassup Fresca? How's life on Tim's keyboard?

[@thenewelegance7772]

my hash rate is 0.053mh/s why ;-; rx 470 4gb binance

[@TheKiryu.]

I've never thought that a fractional knapsack problem could be much easier to solve than a original DP knapsack problem 😂

[@mrolivernone4040]

Hey tim! what's up!

[@HuanYinKoh1995]

Will Dynamic Programming (DP) be explained in the video? hahaha

[@Knuddelfell]

hey there 😃

[@Ben-jw7yw]

Are we just suppose to ignore his cat? 0:09

[@criss5404]

Like for the cat:3

[@flyte9844]

that's a backpack of holding (for the tibia player 🤪)

[@lonelyboy8640]

can you put indonesian text translite plz🥺

[@raghunathmahakud3725]

not clearly able to understand

[@scrutinyng3018]

Bruteforce

[@GenericInternetter]

Hi Tim. Today is my bathday. I like your

[@mastersrikavipriyan280]

9 mins ago.

[@nickchourchoulis]

Yayyy cattt :)

[@pshr2447]

KITTY.

[@AMIN-yn5nl]

😍😍😍♥♥

[@skyricq]

KITTY

[@dydigaming]

First

[@emonymph6911]

Tim, with all due respect. Pretty please invest in a digital inkpad your handwriting is worse then a busy doctors... Writing with the mouse is hard but I think you will be fine with a e-pad.