1
00:00:00,870 --> 00:00:08,100
OK, so now that we talked a little bit about dynamic programming, but preceding that we talked about

2
00:00:08,100 --> 00:00:10,470
both dynamic programming and the greedy method.

3
00:00:11,390 --> 00:00:18,860
We are going to now look at an introductory, greedy method problem, so I'm going to kind of be intertwining

4
00:00:18,860 --> 00:00:20,450
these two things.

5
00:00:21,500 --> 00:00:29,960
The dynamic programming and greedy method just so we can see the goods and the bads of each and when

6
00:00:29,960 --> 00:00:35,630
to use them, what they use for and how sometimes one may prevail over the other.

7
00:00:36,290 --> 00:00:37,820
So let's get started.

8
00:00:37,820 --> 00:00:43,580
This is going to be the first problem for the greedy method, and it's going to be the optimal change

9
00:00:43,580 --> 00:00:44,150
problem.

10
00:00:44,720 --> 00:00:45,830
So let's see what that is.

11
00:00:46,340 --> 00:00:48,320
So here is a problem statement for us.

12
00:00:49,010 --> 00:00:55,850
Let's say we're given an array or vector of money to nominations, so it's like bills or coins.

13
00:00:55,940 --> 00:01:02,390
Specifically, I'm going to be referring to coins and examples in this, but it could be there or so.

14
00:01:03,170 --> 00:01:06,290
Also, let's say they are sorted in ascending order.

15
00:01:06,620 --> 00:01:09,440
So this is a pretty sorted vector or array.

16
00:01:10,330 --> 00:01:13,780
We are also giving a value see for change.

17
00:01:14,230 --> 00:01:22,480
So the question is, how do we find the combination of the minimum possible number of coins, those

18
00:01:22,480 --> 00:01:27,490
coins, but missing coins to create the change?

19
00:01:28,840 --> 00:01:36,340
So basically, what we're trying to see is the optimal combination of these denominations.

20
00:01:36,880 --> 00:01:40,540
If we're meeting a specific amount of change and we're representing that with see?

21
00:01:41,680 --> 00:01:43,900
So let's visualize the problem with an example.

22
00:01:43,930 --> 00:01:46,240
So here we have denominations.

23
00:01:46,450 --> 00:01:55,690
So one, five, 10, 25, 50 and then we say, OK, we need to make 56 change.

24
00:01:55,700 --> 00:02:02,200
So you could say like 56 cents, whatever, but we just need 56, and we need to make that out of these

25
00:02:02,500 --> 00:02:05,140
denominations in the fewest coins possible.

26
00:02:06,260 --> 00:02:09,140
So how would you make 56 and change?

27
00:02:10,280 --> 00:02:16,490
Well, normally what you would do if you're thinking about just your daily life, you probably would

28
00:02:16,490 --> 00:02:22,730
see, OK, I'm just going to start off with the biggest thing I have that is less than what they're

29
00:02:22,730 --> 00:02:28,160
asking for, and I'm just going to make change and kind of go down and be totally right with that.

30
00:02:28,670 --> 00:02:30,470
As far as what we're about to do.

31
00:02:31,630 --> 00:02:38,380
So we start off with 50 because they asked for 56 and change, and we do have a 50 and here, so you

32
00:02:38,380 --> 00:02:47,170
might as well give them that, then we can do a five after that and then we can do a one.

33
00:02:49,190 --> 00:02:54,830
So that's probably what you would do is you'd say, OK, I have a 50 cent piece if we're talking just

34
00:02:54,830 --> 00:02:58,850
like U.S. currency, I have a 50 cent piece after they give them that.

35
00:02:59,090 --> 00:03:04,700
I only need six more, so I'm going to give them a nickel five and then I'm going to give them a penny

36
00:03:04,700 --> 00:03:05,690
to complete it there.

37
00:03:08,060 --> 00:03:09,650
So that would equal 56.

38
00:03:10,730 --> 00:03:12,930
So how does the grilling method relate to this?

39
00:03:12,950 --> 00:03:17,180
Well, you might have noticed that what we did was we just started it the largest number, which is

40
00:03:17,180 --> 00:03:18,510
the right mast in the array.

41
00:03:18,920 --> 00:03:25,460
And then we worked our way down, choosing the biggest values as we went until we satisfy the requirement,

42
00:03:25,460 --> 00:03:26,750
which was 56.

43
00:03:27,380 --> 00:03:30,140
So this is straight up just the definition of the greedy method.

44
00:03:30,140 --> 00:03:33,320
We're always actively choosing the largest possible value.

45
00:03:34,250 --> 00:03:36,300
So here we have our denominations again.

46
00:03:36,320 --> 00:03:37,310
You see what we did.

47
00:03:37,820 --> 00:03:39,470
We said, Hey, we need 56.

48
00:03:39,500 --> 00:03:43,430
So oh, I have 50 cent, why don't I use that?

49
00:03:43,670 --> 00:03:46,330
And this isn't just what you have on hand.

50
00:03:46,340 --> 00:03:48,350
These are the down denominations.

51
00:03:49,130 --> 00:03:54,000
So technically, we're assuming there could be an infinite amount of each one of these.

52
00:03:54,020 --> 00:04:02,150
Imagine just a cash register that's filled with plenty of these denominations of coins that you'll never

53
00:04:02,150 --> 00:04:02,750
run out of.

54
00:04:04,250 --> 00:04:11,360
So I use a 50 and then basically at that point, you know, I only need six left, so I'm not going

55
00:04:11,360 --> 00:04:15,170
to use these because I can't.

56
00:04:15,170 --> 00:04:16,610
That would be given too much change.

57
00:04:16,620 --> 00:04:20,180
So the next thing I can use is a five.

58
00:04:20,900 --> 00:04:22,040
The next biggest thing.

59
00:04:22,520 --> 00:04:26,450
And then I use the one after that because I can't use anything greater than the one.

60
00:04:29,300 --> 00:04:34,400
So let's think about how we did this in our daily lives and come up with an algorithm that's more specific,

61
00:04:34,400 --> 00:04:37,820
so we have the general idea that we're kind of starting over here and working our way down.

62
00:04:39,310 --> 00:04:48,550
So step one, find the largest coin, it doesn't exceed the value of the change needed, and we're representing

63
00:04:48,550 --> 00:04:50,890
change needed as C C is 56.

64
00:04:52,660 --> 00:04:58,090
So we do that, we subtract that coin value from sea.

65
00:04:58,330 --> 00:05:04,750
So we found 50 and that was the largest coin that didn't exceed the value.

66
00:05:04,790 --> 00:05:08,380
It's less than 56 and we subtracted that from it.

67
00:05:08,390 --> 00:05:10,540
So then we just have six.

68
00:05:11,910 --> 00:05:17,970
And then we just keep doing step one and two until there's no more change needed, which is when C is

69
00:05:17,970 --> 00:05:19,410
equal to zero.

70
00:05:20,130 --> 00:05:26,910
So what we did when we just had six left is we found the largest coin that didn't exceed the value of

71
00:05:26,910 --> 00:05:29,400
the change needed, which is the current change.

72
00:05:29,400 --> 00:05:30,660
We only have six left.

73
00:05:31,930 --> 00:05:36,820
So the largest coin that doesn't exceed their value is five, so then we subtracted five, and that

74
00:05:36,820 --> 00:05:41,740
gave us one and then the largest coin it didn't exceed one is one itself here.

75
00:05:42,710 --> 00:05:47,630
So we subtracted that, and then we got to the point where C is now a Sierra, we've given on the change,

76
00:05:47,630 --> 00:05:48,350
so we're done.

77
00:05:51,170 --> 00:05:57,140
So now let's start out with a function definition here on how we would turn this into code.

78
00:05:57,800 --> 00:06:02,840
And let's break down our algorithm into some actual C++ code.

79
00:06:04,370 --> 00:06:14,640
So here I am saying that I'm going to return the vector that contains the answer of all of the denominations.

80
00:06:15,440 --> 00:06:20,810
So you might also be asked to just return the like.

81
00:06:20,810 --> 00:06:27,110
Let's say you're being asked for a function that does what the problem statement describes.

82
00:06:27,650 --> 00:06:32,660
Sometimes you might just be asked to return the minimum number of coins.

83
00:06:32,670 --> 00:06:37,790
So it's like the count in which our case, it would just be the size of the vector because what we're

84
00:06:37,790 --> 00:06:46,370
doing is trying to record the actual combination of the coins that we used for change and store that

85
00:06:46,370 --> 00:06:47,000
in a vector.

86
00:06:47,000 --> 00:06:49,370
So that's what we're solving in this problem.

87
00:06:49,370 --> 00:06:57,260
But if they also wanted to know how many coins were used, what was the minimum amount of coins, then

88
00:06:57,620 --> 00:07:02,330
we kind of already solved that with the fact that we have them in the vector so we can just reference

89
00:07:02,330 --> 00:07:04,640
the vector size to get that answer as well.

90
00:07:05,630 --> 00:07:06,950
So let's continue on here.

91
00:07:06,950 --> 00:07:10,400
I've defined the optimal change function.

92
00:07:10,760 --> 00:07:19,010
We get past our vector of denominations here, and then we also get past an integer see, which is the

93
00:07:19,280 --> 00:07:22,220
change that we need to make from that denominations.

94
00:07:24,290 --> 00:07:30,200
So first thing we're going to do is just make an empty vector to store our optimal combination of denominations,

95
00:07:30,200 --> 00:07:32,420
and that's just being called solution here.

96
00:07:33,500 --> 00:07:35,780
So what is the next thing we need to do?

97
00:07:36,410 --> 00:07:42,860
Well, we need to move through our denominations starting the largest right, the rightmost, so we

98
00:07:42,860 --> 00:07:45,890
can use a for loop for that where we start at the end.

99
00:07:46,100 --> 00:07:49,910
This is just range based, but we're starting at the far right.

100
00:07:50,510 --> 00:07:52,810
So that's denominate size minus one.

101
00:07:52,820 --> 00:07:53,810
That's the last item.

102
00:07:53,810 --> 00:07:58,670
And then we're going to the left with the R minus minus.

103
00:07:58,970 --> 00:08:01,940
As long as I is greater than or equal to zero because so.

104
00:08:03,410 --> 00:08:08,780
We're just moving through our denominations kind of like we were when we were just kind of doing our

105
00:08:09,080 --> 00:08:12,260
normal algorithm there in the previous slides.

106
00:08:14,670 --> 00:08:20,180
So we keep using the largest coin that doesn't exceed the value of the change needed, and that's like

107
00:08:20,190 --> 00:08:21,510
the current change needed.

108
00:08:21,870 --> 00:08:24,120
So Sea Eagles current change needed.

109
00:08:25,220 --> 00:08:30,320
So this is while we can just use a while loop, and this is because we might want to use multiple of

110
00:08:30,320 --> 00:08:31,310
one denomination.

111
00:08:31,640 --> 00:08:35,750
So you notice that we're at a specific denomination, didn't I?

112
00:08:36,350 --> 00:08:38,480
So let's say that was like 10 or something.

113
00:08:39,390 --> 00:08:46,260
Well, we you might think, oh, we can just put in for something, but maybe it's optimal to use multiple

114
00:08:46,260 --> 00:08:47,970
dimes or something like that.

115
00:08:48,480 --> 00:08:52,590
So as long as it is the largest thing that we can keep using.

116
00:08:53,780 --> 00:08:55,190
We're going to keep using it.

117
00:08:55,580 --> 00:09:01,880
So this enables us to use multiple of the same type of denomination.

118
00:09:02,900 --> 00:09:05,360
So I'll see greater than or equal to domination.

119
00:09:07,040 --> 00:09:12,120
We're going to subtract the coin value from see like we just talked about in the previous slides.

120
00:09:12,890 --> 00:09:15,260
So let's just see, we'll see minus two nominations.

121
00:09:15,590 --> 00:09:19,010
That's us taking the coin away from our current change needed.

122
00:09:20,150 --> 00:09:24,150
And then we're going to add that denomination to our solution.

123
00:09:24,260 --> 00:09:29,740
So we're going to push it back to the solution factor because that's one of the coins that we used to

124
00:09:29,750 --> 00:09:33,080
since we already subtracted it from our change needed.

125
00:09:34,580 --> 00:09:39,410
And that's really all we do, we go through our vector.

126
00:09:39,680 --> 00:09:42,440
So think back to the previous slides.

127
00:09:44,320 --> 00:09:49,840
We went through our vector, we started on the right right here, and then we just moved to the left

128
00:09:50,470 --> 00:09:53,020
and we're just this is already pretty sorted.

129
00:09:53,020 --> 00:09:56,260
So what we're trying to do is just use the biggest value possible.

130
00:09:56,260 --> 00:10:01,390
Is this greater than the current change that we still need to give?

131
00:10:02,290 --> 00:10:07,560
If not, then let's use it if it is greater than we just keep moving through the loop.

132
00:10:07,580 --> 00:10:09,370
So that's what the for loop is.

133
00:10:11,680 --> 00:10:17,650
And then the while loop here was just us using multiple of the double now denomination if we need to

134
00:10:17,650 --> 00:10:18,820
like or was talking about.

135
00:10:18,820 --> 00:10:21,300
So we push that back and that's really all we need to do.

136
00:10:21,310 --> 00:10:23,980
And so then we can just return our solution.

137
00:10:25,920 --> 00:10:31,440
So this would be some awful example code right here, and you can write this out and tested if you like.

138
00:10:33,300 --> 00:10:40,320
It just prototypes, the function we were talking about here is the same function here in just actual

139
00:10:40,320 --> 00:10:42,000
C++ code in a file.

140
00:10:42,630 --> 00:10:48,460
And then here's just a main function that uses our example with the denomination's.

141
00:10:48,540 --> 00:10:51,270
So it just initialize this that on line 20.

142
00:10:51,870 --> 00:10:56,120
And then we just have this loop that's printing out what our answer was.

143
00:10:56,130 --> 00:11:04,140
So we're looping over the actual items inside of what was returned by the optimal change function.

144
00:11:05,720 --> 00:11:10,700
And we're just pointing that out with some spaces, so you can run this, and it should give the proper

145
00:11:10,700 --> 00:11:20,150
example, which I believe was if we're using 56, that was just 50 and then five and then one.

146
00:11:22,100 --> 00:11:23,630
So pretty cool.

147
00:11:23,930 --> 00:11:28,280
It's a nice algorithm, but unfortunately there is a problem.

148
00:11:29,420 --> 00:11:36,800
So what if the denominations vector or array was something like this?

149
00:11:37,400 --> 00:11:39,770
One eight nine 14?

150
00:11:39,980 --> 00:11:42,140
You might be saying, well, that doesn't make sense.

151
00:11:42,140 --> 00:11:43,920
Like what type of money is like that?

152
00:11:43,940 --> 00:11:48,740
Well, we want something that can be used for any type of situation.

153
00:11:48,740 --> 00:11:54,590
This problem could be applicable in more ways than just going over popular known currencies.

154
00:11:55,250 --> 00:12:03,170
So let's just say that we're required to do it for any type of theoretical hypothetical denominations

155
00:12:03,170 --> 00:12:05,360
that could be created in a currency.

156
00:12:06,290 --> 00:12:14,600
So if we have one, eight, nine and 14 and they say, OK, well, I want you to come up with 17 change

157
00:12:14,600 --> 00:12:20,360
from these denominations, what is the minimum number of coins that you can use to make change?

158
00:12:20,930 --> 00:12:26,690
So I want you to maybe pause the video right now and see if you can figure that out.

159
00:12:28,240 --> 00:12:36,730
Well, so if you looked over that you probably said, well, the answer is two coins we can use and

160
00:12:36,730 --> 00:12:38,560
nine and eight.

161
00:12:39,010 --> 00:12:41,200
And that gives us 17.

162
00:12:42,170 --> 00:12:45,320
Is this what our greedy algorithm would choose, though?

163
00:12:45,530 --> 00:12:51,830
Think about it, so just pause the video if you need to again and try and go through this the nominations

164
00:12:51,830 --> 00:12:53,870
and see what our greedy algorithm would do.

165
00:12:55,910 --> 00:12:59,480
So actually, unfortunately, the answer is no.

166
00:12:59,570 --> 00:13:08,150
Our greedy algorithm would choose the combination 14 plus one plus one plus one equals 17, which is

167
00:13:08,150 --> 00:13:11,220
four coins instead of two coins and therefore is served.

168
00:13:11,270 --> 00:13:13,490
Optimal is not an optimal solution.

169
00:13:15,250 --> 00:13:22,150
So and you can test this out as well, you can just basically go in and replace it in that code in the

170
00:13:22,150 --> 00:13:25,360
previous slide, you can replace the vector with this hard coded.

171
00:13:27,120 --> 00:13:32,460
Section right here and then also replace the seat that's been passed to the function was 17 instead

172
00:13:32,460 --> 00:13:37,290
of 56, and you should see that this gets printed out right here.

173
00:13:38,970 --> 00:13:41,380
So what are we going to do now?

174
00:13:41,400 --> 00:13:47,610
We just thought we had this cool algorithm, and now we realize that it doesn't necessarily always produce

175
00:13:47,610 --> 00:13:49,620
the optimal solution we were hoping for.

176
00:13:50,910 --> 00:13:55,890
So the good news is there's a fix we can actually use dynamic programming, which we've already talked

177
00:13:55,890 --> 00:13:57,570
about a bit to solve this.

178
00:13:58,590 --> 00:14:03,090
And so since this lecture is taken a little bit of time and I don't want to combine too much in one,

179
00:14:03,420 --> 00:14:07,860
I'm going to go ahead and go over that in the next lecture, so I will see you in the next lecture.