Greedy Algorithms Explained

Aug 15, 2023

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” https://algoexpert.io/techwithtim

📄 Resources 📄
Definitions From: https://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 \u0026 Merch 💰
💻 The Fundamentals of Programming w/ Python: https://tech-with-tim.teachable.com/p…
👕 Merchandise: https://teespring.com/stores/tech-wit…

🔗 Social Medias 🔗
📸 Instagram: https://www.instagram.com/tech_with_tim
📱 Twitter: https://twitter.com/TechWithTimm
⭐ Discord: https://discord.gg/twt
📝 LinkedIn: https://www.linkedin.com/in/tim-rusci…
🌎 Website: https://techwithtim.net
📂 GitHub: https://github.com/techwithtim
🔊 Podcast: https://anchor.fm/tech-with-tim

🎬 My YouTube Gear 🎬
🎥 Main Camera (EOS Canon 90D): https://amzn.to/3cY23y9
🎥 Secondary Camera (Panasonic Lumix G7): https://amzn.to/3fl2iEV
📹 Main Lens (EFS 24mm f/2.8): https://amzn.to/2Yuol5r
🕹 Tripod: https://amzn.to/3hpSprv
🎤 Main Microphone (Rode NT1): https://amzn.to/2HrZxXc
🎤 Secondary Microphone (Synco Wireless Lapel System): https://amzn.to/3e07Swl
🎤 Third Microphone (Rode NTG4+): https://amzn.to/3oi0v8Z
☀️ Lights: https://amzn.to/2ApeiXr
⌨ Keyboard (Daskeyboard 4Q): https://amzn.to/2YpN5vm
🖱 Mouse (Logitech MX Master): https://amzn.to/2HsmRDN
📸 Webcam (Logitech 1080p Pro): https://amzn.to/2B2IXcQ
📢 Speaker (Beats Pill): https://amzn.to/2XYc5ef
🎧 Headphones (Bose Quiet Comfort 35): https://amzn.to/2MWbl3e
🌞 Lamp (BenQ E-reading Lamp): https://amzn.to/3e0UCr8
🌞 Secondary Lamp (BenQ Screenbar Plus): https://amzn.to/30Dtafi
💻 Monitor (BenQ EX2780Q): https://amzn.to/2HsmUPZ
💻 Monitor (LG Ultrawide 34WN750): https://amzn.to/3dSD7tS
🎙 Mic Boom Arm (Rode PSA 1): https://amzn.to/30EZw9m
🎚 Audio Interface (Focusrite Scarlet 4i4): https://amzn.to/2TjXsih

💸 Donations 💸
💵 One-Time Donations: https://www.paypal.com/donate?hosted_…
💰 Patreon: https://www.patreon.com/techwithtim
◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️◼️

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

⭐️ Hashtags ⭐️
#TechWithTim #GreedyAlgorithms

Content

2.86 -> [Music]

8.559 -> hello everybody and welcome to another

10.24 -> youtube video so in today's video i'm

12.799 -> going to be explaining greedy algorithms

15.28 -> now this is really meant to just be an

16.56 -> introduction to this topic so in this

18.64 -> video i will explain to you what a

20.24 -> greedy algorithm is how you can go about

22.48 -> creating a greedy algorithm and then

24.16 -> show you a few examples of it but with

26.4 -> that said if you want to learn more and

28.08 -> practice with greedy algorithms what you

30.24 -> can do is check out the sponsor of this

32.399 -> video before we get started i need to

34.559 -> thank the sponsor of this video which is

36.48 -> alcoexpert algo expert is the best

39.04 -> platform to use from preparing for your

40.719 -> software engineering coding interviews

42.64 -> and has the highest quality coding

44.239 -> interview practice questions with 160

46.879 -> practice questions detailed solutions in

49.28 -> nine of the most popular programming

50.96 -> languages a feature-packed browser-based

53.52 -> coding environment extensive test suites

55.76 -> and conceptual overviews and code

57.36 -> walkthroughs for each and every problem

59.6 -> algo expert is the best resource to use

61.6 -> to ace your coding interviews algo

63.76 -> expert also has a data structures crash

65.76 -> course coding interview assessments and

67.52 -> a mock interviews feature i can highly

70 -> recommend algo expert as a former

71.76 -> customer myself and now an official

73.76 -> instructor on the platform get started

76.159 -> using algo expert today by clicking the

78 -> link in the description and using the

79.759 -> code tech with tim for a discount on the

81.92 -> platform so i'm here on my drawing

84.08 -> tablet and i'm going to start explaining

85.6 -> to you what greedy algorithms are now

87.92 -> before i do that i will note that i do

89.759 -> have very messy handwriting so please

91.68 -> excuse me i'll try my best to make

93.2 -> everything as neat as possible in this

94.96 -> video with that said what is a greedy

97.759 -> algorithm well a greedy algorithm is

100.24 -> really an algorithm that makes a greedy

102.479 -> choice you can think of this as kind of

103.84 -> an optimal choice at every single step

106.72 -> in the solution or in the problem now

109.2 -> the greedy choice is defined by some

111.52 -> rule that rule could be select the

113.36 -> largest number select the smallest

115.04 -> number select the element that has a

117.119 -> certain property whatever you're making

119.439 -> some definitive choice some greedy

121.68 -> choice at every step in the algorithm

124 -> now greedy algorithms can be very

125.36 -> complicated they can also be quite

126.96 -> simple to give you an explanation or

129.039 -> kind of an example of a greedy algorithm

131.12 -> let me kind of introduce a problem to

132.72 -> you right here so let's say for this

134.56 -> problem we're given some array and this

136.72 -> array is filled with integers so i have

138.64 -> 3 4 negative 1 2

141.52 -> negative 3

142.879 -> and 0 and then maybe we're given some

144.8 -> integer n we can say here that n is

147.28 -> equal to 4. now what this problem is

149.599 -> asking us to do is to find the n numbers

152.879 -> in this array that equal the largest sum

156 -> now if that's the case the greedy

158.16 -> algorithm approach to solving this

159.92 -> problem is to simply select the largest

162.64 -> number at every single step until we've

165.28 -> selected n numbers and this should

167.519 -> hopefully solve the problem for us so if

169.68 -> we apply the greedy algorithm approach

171.92 -> we're selecting the largest number at

173.519 -> every step until we've hit four numbers

176.319 -> so what we do is we start by selecting

178.4 -> four because this is the current largest

180.56 -> number so we select four then we select

183.519 -> 3 because 4 was already selected so now

185.76 -> we have 3 and 4.

187.76 -> then we select 2

190.08 -> and then finally we select 0 and what we

193.44 -> get is 4 3 2 and 1 which means that we

197.04 -> have an answer of 10.

199.68 -> so that's the largest sum that we can

201.28 -> create by selecting four numbers and

203.599 -> this would actually be our answer here

205.44 -> we would return 4 3 2 and 1. so that's

208.4 -> an example of a very very simple greedy

210.879 -> algorithm where all we did was select

212.879 -> the largest number at each step and well

214.959 -> that led us to the solution so i know

217.599 -> the example i just showed you is

218.959 -> relatively trivial but it's the best way

220.879 -> that i can show you what a greedy

222.56 -> algorithm is without getting into any

224.64 -> super formal explanations so as you saw

227.28 -> there a greedy algorithm is really just

229.36 -> an algorithm that makes an optimal or

231.44 -> greedy choice at every single step and

234.239 -> eventually all of those choices lead to

236.56 -> an optimal solution at the end of the

238.72 -> program now before we get into some more

240.72 -> advanced examples here i'm going to give

242.48 -> you two kind of formal definitions or

245.04 -> formal properties of when you can

246.879 -> actually use a greedy algorithm to solve

248.879 -> a problem so if the following two

250.64 -> properties that i'm going to state are

251.84 -> true you can use a greedy algorithm and

253.599 -> you'll be able to solve the problem so

255.92 -> the first property is called the greedy

257.759 -> choice property and what this says is

259.759 -> that a global optimal solution can be

262.72 -> reached by choosing the optimal choice

264.8 -> at each step and then the second

266.8 -> property that needs to be true as well

268.72 -> is the optimal substructure property

271.12 -> which says a problem has an optimal

273.28 -> substructure if an optimal solution to

275.84 -> the entire problem contains the optimal

278.56 -> solutions to the subproblems so to kind

281.28 -> of break that down a little bit what

283.04 -> that means is every time you make a

284.72 -> choice you can kind of treat that as a

286.56 -> sub problem now an optimal substructure

289.68 -> exists if all of those sub problems

292.16 -> allow you to solve the larger problem as

294.96 -> a whole so really it's saying if all of

296.96 -> the solutions to these sub problems

299.12 -> combined allow you to have a full

301.28 -> optimal solution to the entire problem

304 -> then you're good you can go ahead and

305.52 -> use a greedy algorithm so i'll leave

307.36 -> those definitions on the screen so that

308.8 -> you can read them i'll give you one more

310.479 -> kind of formal definition here before we

312.32 -> get into another example this says

314.56 -> greedy algorithms work on problems for

316.72 -> which it is true that at every step

318.8 -> there is a choice that is optimal for

320.639 -> the problem up to that step and after

323.36 -> the last step the algorithm produces the

325.6 -> optimal solution of the complete problem

328.32 -> so that makes it seem a little bit more

329.6 -> confusing than it really is what i'm

331.36 -> going to do now is move on to another

332.96 -> example and show you how we apply a

334.639 -> greedy algorithm to it so in front of me

336.8 -> i have a very famous problem which is

338.8 -> known as the knapsack problem now what

341.28 -> i'm going to do is introduce a variation

343.12 -> of this problem to you and then explain

345.039 -> how a greedy algorithm can be used to

347.039 -> solve this then i'm going to go back to

349.12 -> kind of the original problem and show

350.88 -> you how the greedy algorithm fails so

353.36 -> let me introduce what this problem is so

355.52 -> in this problem you have a backpack that

357.68 -> has a specific capacity in this case the

360.08 -> capacity is 25. now that denotes kind of

362.96 -> the size in total of items that you can

365.52 -> hold in the backpack some people call it

367.6 -> weight you can call whatever you want

369.44 -> but that means that we can only store at

371.039 -> most 25 kind of you know units of items

374.72 -> in our backpack and what our goal is is

377.6 -> to fill the backpack with as much value

379.84 -> as possible without going over its

381.919 -> capacity so we can see that each item

384 -> has a size here and has a value so if

387.039 -> we're looking at item 0 it has a size of

389.84 -> 22 and it has a value of 19.

393.28 -> we look at item 1 we have a size of 10

396.16 -> and a value of 9. and so if we were to

398.56 -> select say item 1 that means that we

400.72 -> would then be left with 15 units of

403.28 -> capacity in our backpack we would have a

405.759 -> total value of 9. so again the goal is

408.319 -> to maximize the value without going over

410.56 -> the capacity but you can be at the

412.479 -> capacity so you could use 25 units of

415.28 -> space in the backpack so the question

418.08 -> here is how do we use a greedy algorithm

420.56 -> to solve this problem and actually i

422.24 -> need to introduce the variation of this

423.84 -> problem which is you can select a

426.16 -> fractional amount of any of these items

429.84 -> so what that means is that let's say we

431.36 -> want to select item one but we don't

433.44 -> have enough room for the entirety of

435.599 -> item one we can select half of item one

438.8 -> so if we were going to select half of

440.24 -> item one then what we would do is you

442.16 -> know say 0.5 times 10 that's how much

444.96 -> weight we're going to have for half of

446.639 -> item 1 and then 0.5

449.12 -> times nine that's how much value we're

451.039 -> gonna get if we select a fractional

452.8 -> amount of item one now you don't have to

454.88 -> just select half you could select 99 of

457.28 -> it you could select one percent of it

459.12 -> you could select ten percent of it

460.479 -> whatever you want you can select a

462 -> fractional amount of an item so my

464.639 -> question is how do we use a greedy

466.56 -> algorithm to solve this fractional

468.479 -> backpack problem well the first thing

470.639 -> that we should consider

472 -> is can we solve this problem by just

474.479 -> looking at one of these columns here so

476.879 -> just the value or just the size can i

479.28 -> select items that just have the largest

481.12 -> value can i select items that have the

484 -> smallest size what is kind of the grady

486.639 -> approach so let's just see what happens

488.479 -> if we try to select items that have the

490.56 -> smallest size first and see if that

492.56 -> actually gives us an optimal solution so

495.12 -> at each step in our algorithm we're

497.039 -> going to select the remaining item that

499.199 -> has the smallest size that's kind of our

501.199 -> greedy step and so the first item that

503.44 -> we're going to select here is going to

504.879 -> be item 3 because it has a size of 7.

508.16 -> so when we do that we see that our

509.919 -> current size is going to be 7 and our

512.32 -> current value is going to be 6 and then

514.159 -> we can cross this off because we've used

515.919 -> it

516.64 -> okay the next greedy step is we are

518.959 -> going to select the size of nine so we

521.839 -> select nine that gives us a total size

524.08 -> of 16 and then our value is now 15

526.72 -> because well

527.839 -> 9 plus 6 is 15

530.08 -> okay and then we're going to select our

531.76 -> next item the next item has a size of

534.64 -> 10. and when we select this item we see

536.959 -> that this is going to lead us to go over

538.56 -> capacity to 26 so what we need to do is

541.04 -> select a fractional amount of this item

543.279 -> which means instead of selecting all 10

545.2 -> we're going to select 90 of this right

547.04 -> so we'll select 9 of 10 which means we

550.32 -> are going to get

551.92 -> now a capacity of 25 and then what's 90

555.2 -> of 9 well let me just use the calculator

557.44 -> to get that i probably should have been

559.279 -> able to solve that in my head but that's

560.64 -> going to give us 8.1 value which means

563.76 -> we're going to have a total value of

565.519 -> 23.1

567.6 -> perfect so there you go we now have a

569.92 -> total capacity of 25 a value of 23.1

573.92 -> and that's kind of the answer we got

575.519 -> when we selected items that had the

577.12 -> smallest size that was the greedy choice

579.2 -> that we made so let me just kind of move

581.36 -> this over to the side here so we

582.88 -> remember this value and now let's try it

585.2 -> in the other way all right so now we're

586.56 -> going to perform the greedy algorithm

588.24 -> but this time choosing the largest value

590.8 -> instead of the smallest size so if i'm

592.8 -> selecting the largest value that means

594.64 -> i'm going to select item 0. so we have a

597.68 -> size of 22 and a value of 19.

602.56 -> then i'm going to be choosing between

603.839 -> item one and item two because they have

605.76 -> the same largest value since this has a

608.88 -> smaller size item two i'm going to

610.48 -> select this one and so that means that

612.959 -> if i were to select the entire item i

614.48 -> would have a weight of 31. obviously i

617.04 -> can't do that because that goes over my

618.72 -> capacity and so instead i need to select

621.2 -> 33

622.56 -> of this item so that means that my

625.04 -> capacity is going to go to 25. 33 of 9

627.68 -> is clearly 3. same thing here that means

630.48 -> that i am going to get

632.399 -> an additional 2 value here and that is

635.04 -> going to lead me to 22. so let's take

638 -> this and store this down here as well so

640.16 -> the two answers we got were 23.1 and 22.

643.6 -> now what we can say right now is okay

645.2 -> well clearly the other approach

646.56 -> selecting the smallest size worked

648.24 -> better for this example but is this

650.64 -> actually the optimal answer are either

652.88 -> of these the optimal answer to this

654.88 -> problem and well the answer to that is

657.04 -> no there's actually a better way to

658.72 -> solve this still using a greedy approach

661.44 -> but it requires a little bit of thinking

663.2 -> so the purpose of me showing you those

664.8 -> two methods there was to illustrate that

666.64 -> in a lot of examples you can use a

668.64 -> greedy algorithm but you have to make

670.72 -> sure you're really thinking about what

672 -> your greedy criteria is how you're

674.88 -> selecting the optimal choice at every

677.12 -> single step now for this problem here

679.12 -> you have to remember that we can select

681.04 -> a fractional amount of all of these

683.839 -> items and so really what we should do is

686.399 -> find the items that have the best value

689.04 -> to size ratio select the largest

692 -> fractions of those items that we can and

694.56 -> then continue on throughout the yellow

696.959 -> group so i'll show you what i mean by

698.399 -> that but let's just have a look here so

699.839 -> what i'm going to do is make another

701.279 -> column and i'm going to call this value

704.56 -> over size now the point of this is that

707.2 -> the items that have the largest value

709.36 -> over size ratio are the best items for

712 -> me to select

713.279 -> so quite simply if we're looking at this

714.959 -> right here nine size gives me nine value

717.76 -> that means my value to size ratio is one

720.48 -> so for every extra capacity i add or

723.04 -> remove i guess from my backpack i get

725.2 -> one value whereas if we're looking at

727.2 -> say 22 and 19 i need to pull out my

729.279 -> calculator for this but 19 divided by 22

732.32 -> is 0.8636

736.639 -> if we're looking at

738.24 -> 9 and 10 we're going to get 0.9 and if

741.68 -> we're looking at 6 and 7 then we're

744.079 -> going to get 0.857

748.16 -> so here we can see that the best item to

750.959 -> select in terms of the value to size

752.8 -> ratio is going to be item 2 and then

755.279 -> we're going to have item 1 and then it's

757.76 -> going to be item 0 followed by item 3.

761.2 -> so now what our new greedy algorithm

763.36 -> should do here the correct greedy

764.88 -> algorithm is at each step in our

766.88 -> algorithm we should select the item that

768.88 -> has the highest value over size ratio

771.6 -> and take as much of that item as we

773.76 -> possibly can so in this case we see that

776.56 -> this is our best item so we're going to

778.16 -> take all of item two so i can just i

781.76 -> guess write

782.959 -> what our weight and our size is going to

784.56 -> be over here so that's item 2 we're

786.72 -> going to select all of that

788.72 -> then this guy is done so what's the next

790.639 -> one well we want to select item one so

793.2 -> we're going to select all of item 1

794.639 -> which means we're going to get now a

795.92 -> capacity of 19 and we're going to have a

798.24 -> value of 18 so this guy's done now and

801.6 -> then this is slightly better than this

804 -> so we're going to select as much of

806.24 -> item zero as we possibly can so we need

808.959 -> to select kind of six size of item zero

812.16 -> so let me do some math here so we're

813.68 -> gonna select approximately 27

816.48 -> of item zero so 27

819.519 -> times 19 gives us a value of

823.16 -> 5.18 which means that we're going to

825.6 -> have here 23. if i can do this correctly

830.44 -> 23.18 like that and then we're going to

833.92 -> have a capacity of 25. so we did

837.279 -> actually end up with marginally more

839.6 -> value by using this different greedy

842.48 -> approach that i just showed you right

844 -> here now a lot of you might think that

845.6 -> this is a calculation error this is not

847.839 -> there is actually slightly more value

850.8 -> in doing the method that i just showed

852.48 -> you here so selecting a fraction of this

855.68 -> specifically 27 of it now in a lot of

858.32 -> other examples you'll see that this

859.6 -> difference would be much larger the

861.68 -> whole point of this was just to

862.959 -> illustrate to you that you need to be

864.639 -> very careful in what you actually use as

866.8 -> your greedy criteria it's not as simple

869.519 -> as just looking at one category in this

871.68 -> case we combined the categories and

873.92 -> intuitively this does make a lot of

876 -> sense right to select the highest

878.16 -> fraction of items that we can that have

880.639 -> the largest value over size right or

883.6 -> value to size ratio so that's the

886.32 -> example that i wanted to show you on how

888.079 -> you can actually use a greedy algorithm

889.76 -> to solve a problem i'm not going to

891.199 -> write the code for this you can figure

892.639 -> that out on your own but now what i want

894.56 -> to do is change the variation of this

896.56 -> problem and show you how a greedy

898.24 -> algorithm might actually fail all right

900.399 -> so i've cleared the screen and now what

901.839 -> i want to do is change the variation of

903.68 -> this problem and show you how the greedy

905.6 -> algorithm will fail when we change the

907.76 -> problem just slightly so now the problem

910.56 -> is the exact same you want to maximize

912.399 -> the value without going over the

913.6 -> capacity however you cannot select a

916.399 -> fractional amount of an item so if we

919.12 -> try to perform the greedy algorithm we

920.639 -> did in the last step where we select the

922.88 -> item that has the largest value to size

926.399 -> ratio you're going to see that we

928 -> quickly fail and we do not get the

930.24 -> correct amount we do not get the largest

932.16 -> value we possibly can so let me prove it

934.399 -> to you this was the item that had the

936.48 -> best us value to size ratio

939.279 -> second best

940.56 -> third best and fourth best

942.639 -> so if we select this item first

944.959 -> we get nine and nine

946.8 -> and then we select this item we get a

949.199 -> total capacity of 19

951.199 -> and then we get a value of 18 and now we

953.6 -> try to select the next item and we see

955.44 -> we cannot select another item because

957.04 -> there is no item that has a size small

959.839 -> enough that we can fit in the bag with a

962.079 -> capacity of 19 already being used and so

965.199 -> our value from the greedy algorithm

967.12 -> approach is 18. so obviously this means

970 -> that the greedy algorithm fails in this

971.92 -> example and cannot deliver an optimal

974.32 -> solution and one of the reasons it can't

976.48 -> do that is because the choice it makes

978.48 -> in the current step actually affects

980.56 -> what choices it's going to have to make

982.32 -> in the future because we have this

984.24 -> capacity constraint and so we really

987.04 -> would be better off using something like

988.48 -> dynamic programming here to solve this

990.639 -> problem

991.759 -> rather than a greedy algorithm in fact a

993.839 -> greedy algorithm just will not give us

996.079 -> the correct result unless we're lucky

997.839 -> and the greedy algorithm choices end up

1000.079 -> lining up with what the actual optimal

1002.079 -> value should be so with that i think i'm

1004.959 -> going to end the video here hopefully

1007.279 -> this gave you a quick introduction to

1008.8 -> what greedy algorithms are again they're

1010.959 -> pretty straightforward but they're used

1012.56 -> in all kinds of different algorithms for

1014.8 -> example if you're talking about

1015.92 -> dijkstra's algorithm or the minimum

1017.68 -> spanning tree algorithm where a lot of

1019.759 -> other graph algorithms actually may use

1022.399 -> a version of a greedy algorithm they

1024.48 -> have other types of kind of algorithms

1026.319 -> in them but they make a greedy choice at

1028.799 -> every single step to help solve the

1030.799 -> problem if you're talking about

1032.079 -> dijkstra's algorithm at every single

1033.76 -> step it's choosing the node that

1035.52 -> currently has the shortest distance to

1037.28 -> get to it and then it's examining from

1039.6 -> that note now might be butchering that a

1041.52 -> little bit it's been a while since i

1042.72 -> looked at dijkstra's but that is an

1044.4 -> example of an algorithm that implements

1046.16 -> a greedy choice and kind of is a greedy

1048.559 -> algorithm based on the definition of

1050.559 -> greedy algorithms anyways i hope you

1052.559 -> guys enjoyed i hope you learned

1053.84 -> something if you did make sure to leave

1055.2 -> a like subscribe to the channel i will

1057.039 -> see you in another youtube video

1059.61 -> [Music]

1067.12 -> you

Source: https://www.youtube.com/watch?v=lfQvPHGtu6Q