1
00:00:01,170 --> 00:00:01,590
OK.

2
00:00:01,620 --> 00:00:12,480
Welcome to this final slide show lecture for this optimization subsection of the course, we're going

3
00:00:12,480 --> 00:00:17,730
to be talking about one last problem and this is the oh one knapsack problem you might have heard of

4
00:00:17,730 --> 00:00:20,550
it before might have not, which is totally fine if you haven't.

5
00:00:22,050 --> 00:00:25,530
And there will be one lecture after this which will be about the code for this.

6
00:00:25,530 --> 00:00:28,650
But we're going to go over the theoretical part of this problem in this lecture.

7
00:00:29,970 --> 00:00:35,400
So this will be a little bit trickier than the other problems is kind of why I am finishing on this

8
00:00:35,700 --> 00:00:43,170
for this sub topic, but I will go into as much detail as I can explaining it, and it's very interesting

9
00:00:43,170 --> 00:00:43,620
problem.

10
00:00:43,660 --> 00:00:45,960
So let's look into it.

11
00:00:46,740 --> 00:00:50,130
Oh, one really just ends for zero one.

12
00:00:50,460 --> 00:00:51,690
True and false?

13
00:00:51,850 --> 00:00:52,230
Kind of.

14
00:00:52,230 --> 00:00:59,310
There are other knapsack problems that are a little bit different.

15
00:00:59,820 --> 00:01:03,510
So pretty much the same overall idea, but they're a little bit different.

16
00:01:03,510 --> 00:01:07,770
So if you'd like to look that up and check into those, I'm not going to be going those, but it might

17
00:01:07,770 --> 00:01:08,880
be good to look into those, too.

18
00:01:08,910 --> 00:01:14,190
This is definitely the most common one, though out of all the SEC problems, so most common one to

19
00:01:14,190 --> 00:01:16,500
be asked in interviews and things like that too, I think.

20
00:01:17,460 --> 00:01:19,200
OK, so let's get started.

21
00:01:20,420 --> 00:01:22,130
So what is the one knapsack problem?

22
00:01:22,160 --> 00:01:28,430
Well, it's basically something like where a thief could enter a home with the goal of stealing as many

23
00:01:28,430 --> 00:01:32,630
things of the most valuable items as he can.

24
00:01:33,950 --> 00:01:38,150
So he's carrying a knapsack with him that has a specific weight capacity.

25
00:01:38,270 --> 00:01:42,740
So if he wants to put too much in this knapsack, it would tear if there was too much weight.

26
00:01:43,760 --> 00:01:49,850
So the problem is, if the thief needs to figure out is what is the best combinations, best combination

27
00:01:49,850 --> 00:01:54,380
of items to maximize the value that he can take from the house.

28
00:01:55,010 --> 00:01:56,600
So he wants the best combinations.

29
00:01:56,930 --> 00:02:02,510
The combination of items that wouldn't exceed the weight and would give him the best value, kind of

30
00:02:02,510 --> 00:02:05,660
the best bang for his bike to get out of the house with.

31
00:02:08,360 --> 00:02:11,170
So just a little bit about what this might look like in code.

32
00:02:11,180 --> 00:02:16,940
The representation of the knapsack would be maybe like a two dimensional array or an array of tuples.

33
00:02:16,940 --> 00:02:20,570
It's just pairs where this is an item right here.

34
00:02:20,600 --> 00:02:22,430
Each item has a weight in a value.

35
00:02:22,460 --> 00:02:26,570
So here's an item, here's an item and so on.

36
00:02:27,560 --> 00:02:29,000
Here's a more concrete example.

37
00:02:29,000 --> 00:02:32,660
So like this will have a weight of three and a value of seven.

38
00:02:32,690 --> 00:02:34,070
So this would be like the first item.

39
00:02:34,340 --> 00:02:39,140
Second item would have a weight of six and a value of five and so on and so forth.

40
00:02:39,530 --> 00:02:44,120
The other thing we need to define is a maximum capacity of our knapsack.

41
00:02:44,150 --> 00:02:46,490
So example would be like seven or something.

42
00:02:48,980 --> 00:02:51,470
So what would a naive solution look like?

43
00:02:51,480 --> 00:02:56,600
So if you just had to think of this off the top of your head and figure out a way that didn't necessarily

44
00:02:56,600 --> 00:03:01,700
have to be the most efficient or anything like that, but you just had to solve the problem.

45
00:03:01,700 --> 00:03:06,650
You just had to make sure that you came up with the optimal combination of items or just.

46
00:03:07,850 --> 00:03:15,650
The best value you could get from the items for putting things in your knapsack with a given of the

47
00:03:15,650 --> 00:03:20,810
given input to the problem, like the given weight capacity, the knapsack and the given set of items.

48
00:03:22,470 --> 00:03:29,340
So what would be the most basic implementation, so it's actually you can do it in like a brute force

49
00:03:29,340 --> 00:03:36,300
manner and get the optimal combination, you just have to iterate over all possible combinations, basically.

50
00:03:37,960 --> 00:03:42,370
So that would look something like this, this is a recursive solution.

51
00:03:42,580 --> 00:03:47,560
I'm not going to go into great detail about this because I think that you could come up with some of

52
00:03:47,560 --> 00:03:50,140
your own ways of doing this, but I just wanted to mention it.

53
00:03:51,890 --> 00:03:56,600
The least just mentioned a brute force solution, because I feel like it was important to the overall

54
00:03:56,600 --> 00:04:02,450
problem, you know, comparing the different ways of solving this and which ways of solving this could

55
00:04:02,450 --> 00:04:05,840
be more efficient and as far as time and stuff like that.

56
00:04:07,620 --> 00:04:13,470
So we have this function here, it is recursive, it has a base case up here in is representative of

57
00:04:13,470 --> 00:04:18,740
the number of items items is a to do list, which is just a list of pairs.

58
00:04:18,750 --> 00:04:24,150
It's actually like a list that has other tiny lists that are just the weight and the value.

59
00:04:24,480 --> 00:04:29,160
So you see of this thing right here, like the second index here of items, this zero would be the weight

60
00:04:29,700 --> 00:04:32,280
one would be the value just like up here.

61
00:04:32,700 --> 00:04:35,070
You notice like this is index zero.

62
00:04:35,280 --> 00:04:37,500
This is you could see this instead of a tuple.

63
00:04:38,670 --> 00:04:39,930
Just to have brackets.

64
00:04:39,930 --> 00:04:44,250
And this would be a list within a list and it just has zero is the weight.

65
00:04:44,700 --> 00:04:45,930
One is the value.

66
00:04:48,360 --> 00:04:56,160
So you will be the given capacity and a certain, you know, of course, the recursion is changing this.

67
00:04:56,160 --> 00:05:02,880
So it's whatever stack, frame or whatever function call recursive call we're in, it's the given the

68
00:05:02,880 --> 00:05:06,720
given max capacity at that point of the or not the max.

69
00:05:06,720 --> 00:05:12,570
But just like the given capacity that's being considered at this point, but we do have a max capacity

70
00:05:12,570 --> 00:05:15,180
of our knapsack that's represented by W.

71
00:05:16,380 --> 00:05:20,550
So of course, if in a zero w zero, we return to zero, that's our overall base case.

72
00:05:21,000 --> 00:05:30,540
Then here we're checking to see that when we look at the minus one item, the weight of that, if it's

73
00:05:30,540 --> 00:05:37,020
greater than the overall capacity, then we return recursive call and we just go kind of.

74
00:05:39,560 --> 00:05:45,380
To that next items, so be considering like the next one will do it in minus one.

75
00:05:47,380 --> 00:05:55,810
So the next part here is just doing a first in a second, which these two things are basically just

76
00:05:57,130 --> 00:06:01,450
us considering using an item in us considering not using an item.

77
00:06:02,020 --> 00:06:08,980
So you notice that this is like a value of an item being added to a recursive call where we then basically

78
00:06:09,280 --> 00:06:11,050
call it with that item.

79
00:06:11,830 --> 00:06:12,460
So.

80
00:06:14,450 --> 00:06:18,740
That's why we have the max capacity minus the items wait right here.

81
00:06:20,100 --> 00:06:26,400
So this is like adding that item to the value, adding the value of the item to our overall value because

82
00:06:26,400 --> 00:06:30,480
you know that that's what we're returning, it's like our overall value, we're trying to find the optimal

83
00:06:30,480 --> 00:06:30,930
value.

84
00:06:33,010 --> 00:06:39,160
So this is like the items value, and we're adding it to the recursive call, since we're returning

85
00:06:39,160 --> 00:06:46,240
the value and in the recursive call here, since we're considering that item, we're going to basically

86
00:06:46,240 --> 00:06:51,010
now consider a different state of our knapsack that now has that item in it.

87
00:06:51,020 --> 00:06:56,950
So right here, we need to subtract that from the overall weight, say the overall capacity, because

88
00:06:56,950 --> 00:07:00,850
of course, if we add a new item to our knapsack, we've got to adjust the capacity like if it had a

89
00:07:00,850 --> 00:07:06,010
way to for that item, had a way to for now, our capacity and our capacity is for less than it was

90
00:07:06,010 --> 00:07:06,720
previously, right.

91
00:07:06,730 --> 00:07:10,420
So that's what we're doing right here or passing that for a W..

92
00:07:10,540 --> 00:07:15,970
And then, of course, we just pass our container of items and then we use the N minus one, which is

93
00:07:15,970 --> 00:07:17,380
current item we're considering.

94
00:07:20,180 --> 00:07:24,470
So the second thing that was like, if we consider the item for first, the second is if we don't consider

95
00:07:24,470 --> 00:07:25,880
when we just move on to the next item.

96
00:07:26,450 --> 00:07:28,910
So here we have a check.

97
00:07:29,060 --> 00:07:30,560
This is kind of where it happens.

98
00:07:30,560 --> 00:07:37,610
It's like post condition after recursion is saying, Well, if considering the item is greater than

99
00:07:37,610 --> 00:07:40,850
not considered an item, then we'll return considering the item.

100
00:07:41,180 --> 00:07:43,520
Otherwise, we'll return, not considering the item.

101
00:07:44,690 --> 00:07:50,090
So that's just like the part that figures out what the better option is, whether to put an item in

102
00:07:50,090 --> 00:07:54,080
the knapsack or not put an item in the knapsack if it yields a better value or not.

103
00:07:54,650 --> 00:08:00,260
So we're just using recursion to iterate over all the possible combinations that can ever be in the

104
00:08:00,260 --> 00:08:03,260
knapsack to find the best solution and return the value.

105
00:08:03,810 --> 00:08:08,840
You know, how much do all those items values add up to for the best knapsack?

106
00:08:09,950 --> 00:08:11,660
OK, so that's just the basic explanation.

107
00:08:11,660 --> 00:08:16,850
If you want to go in and like, draw a recursive tree for this, you could definitely do that and see

108
00:08:16,850 --> 00:08:17,600
how it's working out.

109
00:08:17,600 --> 00:08:22,730
But like I said, I'm not going to go into great detail about this because we have some other solutions

110
00:08:22,730 --> 00:08:25,280
that can consider that are going to be better than this.

111
00:08:25,280 --> 00:08:27,270
And why are they going to be better than this?

112
00:08:27,290 --> 00:08:28,790
Well, let's check that out in the next slide.

113
00:08:30,260 --> 00:08:31,700
So this is pretty slow.

114
00:08:32,570 --> 00:08:38,030
So since we're iterating over all the subsets of all the items and we can choose or not choose one.

115
00:08:38,660 --> 00:08:42,380
This gives us actually two to the N combinations that we have to explore.

116
00:08:43,450 --> 00:08:50,230
We're in the number of items, and so it also ends up being bigger of two to the N, that's exponential

117
00:08:50,230 --> 00:08:54,880
time complexity and that is a very, very poor time complexity in terms of efficiency.

118
00:08:55,180 --> 00:08:57,580
So there's got to be some other solutions that are better, right?

119
00:08:57,940 --> 00:08:59,140
Some faster solutions.

120
00:09:00,130 --> 00:09:02,050
So what if we were to go with a greedy method?

121
00:09:02,890 --> 00:09:03,760
How do we do that?

122
00:09:03,770 --> 00:09:12,910
So if we care about looking at the best items in terms of the value to weight ratio and then just starting

123
00:09:12,910 --> 00:09:17,080
at the best and moving towards the worst and just stopping once our knapsack is for that would kind

124
00:09:17,080 --> 00:09:18,610
of be the greedy way of going about it.

125
00:09:19,120 --> 00:09:20,080
So how would we do that?

126
00:09:20,110 --> 00:09:24,610
Well, first we have to sort the knapsack based on value to weight ratio, right?

127
00:09:25,840 --> 00:09:28,030
So we can just sort it.

128
00:09:28,030 --> 00:09:33,130
And then what we'll do is we'll move linearly through that sorted list of the items.

129
00:09:33,460 --> 00:09:36,490
And once we can't add any more to our knapsack, we'll just stop.

130
00:09:36,940 --> 00:09:38,350
So that seems logical, right?

131
00:09:40,180 --> 00:09:46,540
So in terms of speed, two of the fastest growing algorithms are more short and quick sort, and those

132
00:09:46,540 --> 00:09:48,730
are both in log in time complexity.

133
00:09:49,360 --> 00:09:54,370
So we could implement it with either one of those and then we could just use our greedy method as we

134
00:09:54,370 --> 00:09:55,240
move through it.

135
00:09:55,240 --> 00:09:57,160
In a linear fashion, I say linear.

136
00:09:57,160 --> 00:10:03,940
So that is going to be in big of in time complexity since in log in is of a higher magnitude than that,

137
00:10:04,450 --> 00:10:10,120
our time complexity would be capped it in log in for this greedy method we're talking about.

138
00:10:10,330 --> 00:10:12,700
So whether you use a sort of quick sort.

139
00:10:16,040 --> 00:10:17,360
OK, so.

140
00:10:18,410 --> 00:10:20,540
If we do the screamer, so let's see how this will work out.

141
00:10:21,050 --> 00:10:26,240
So here I have my items and I have a max capacity of six in this example.

142
00:10:27,230 --> 00:10:28,280
And hopefully this is correct.

143
00:10:28,280 --> 00:10:32,930
I sorted them based on the value to weight ratio.

144
00:10:34,380 --> 00:10:39,720
So we're going to go ahead and start off on this first item and just move left to right and add things

145
00:10:39,720 --> 00:10:45,750
to our knapsack, so we'll be adding to current weight and adding to best value, and then we'll just

146
00:10:45,750 --> 00:10:48,060
stop once it's about to exceed the knapsack.

147
00:10:48,870 --> 00:10:54,210
So we add two to the weight, nine to the best value for this first item gives us to a nine.

148
00:10:54,760 --> 00:10:59,580
We go to the next one, we add two to our current weight and five to our best value, and that gives

149
00:10:59,580 --> 00:11:05,010
us four and 14 and we move to the next item and Oatway.

150
00:11:05,010 --> 00:11:09,550
If we add four weight to this, our current weight becomes eight.

151
00:11:09,570 --> 00:11:13,290
But we said our knapsack can only hold six, so we actually can't add this item.

152
00:11:13,800 --> 00:11:15,870
So we're not going to consider adding the value either.

153
00:11:15,870 --> 00:11:17,430
So we got to stop at this point.

154
00:11:18,180 --> 00:11:24,510
So we say, Hey, best value is 14, so that's our optimal knapsack value.

155
00:11:25,290 --> 00:11:30,810
But is it our optimal next to grab you when you positivity and take a look and see if this is actually

156
00:11:30,810 --> 00:11:33,360
the best value we could get with these items?

157
00:11:35,390 --> 00:11:41,420
So if you took a look and figured out you wanted to notice that we actually have a better option, if

158
00:11:41,420 --> 00:11:48,620
we did consider that item that we just kind of discarded and stopped at and instead didn't use this

159
00:11:48,620 --> 00:11:50,310
and use the first one and that one.

160
00:11:50,960 --> 00:11:55,850
We noticed that four plus two is six that's still face in our knapsack, but we have nine plus nine

161
00:11:55,850 --> 00:11:58,220
now for our value, which gives us 18.

162
00:11:59,550 --> 00:12:02,160
So 18, obviously greater than 14.

163
00:12:02,880 --> 00:12:08,940
So this greedy method actually did not find this the optimal value for our knapsack.

164
00:12:10,530 --> 00:12:11,610
So what to do now?

165
00:12:11,640 --> 00:12:13,020
This is kind of annoying, right?

166
00:12:13,050 --> 00:12:20,520
Ah, brute force does find the optimal solution because it iterate over all possible combinations,

167
00:12:20,760 --> 00:12:26,290
but it's very slow and our greedy one is pretty fast, you know, rather than having to to the end.

168
00:12:26,730 --> 00:12:31,560
Time complexity, which is exponential ahead in log in, which is based on like merge sort or something

169
00:12:31,560 --> 00:12:32,010
like that.

170
00:12:32,670 --> 00:12:34,530
So it was much faster, but it wasn't optimal.

171
00:12:34,540 --> 00:12:36,180
It didn't give us an optimal answer.

172
00:12:36,870 --> 00:12:38,100
So what else we could do?

173
00:12:38,370 --> 00:12:42,090
And you might already have an answer to this based on what we've done so far.

174
00:12:43,290 --> 00:12:45,180
That would be dynamic programming.

175
00:12:45,210 --> 00:12:47,690
Yes, we'll continue on with dynamic programming.

176
00:12:47,700 --> 00:12:50,790
It is possible to use it to solve this problem in a better way.

177
00:12:53,610 --> 00:12:56,610
So that's cool, but how do we use it for this problem, so.

178
00:12:57,700 --> 00:13:02,740
Yeah, let's remember the ingredients required to use in our program, and so it kind of has two things

179
00:13:02,740 --> 00:13:05,800
that really would make us want to use dynamic programming, right?

180
00:13:06,640 --> 00:13:12,100
Some problems that can be combined to answer an overarching problem and then getting rid of repetition

181
00:13:12,100 --> 00:13:13,030
and redundancy.

182
00:13:13,040 --> 00:13:16,480
So we're not calculating the same problem, same answers over and over again.

183
00:13:17,650 --> 00:13:22,000
So although these may not seem immediately applicable to the problem, they're both present in this

184
00:13:22,010 --> 00:13:22,830
old knapsack.

185
00:13:22,840 --> 00:13:23,620
And let's see why.

186
00:13:25,090 --> 00:13:31,270
So the main concern for any given some problem in this is with a certain amount of space left in a knapsack

187
00:13:31,270 --> 00:13:33,820
in a certain collections of items left to use.

188
00:13:34,030 --> 00:13:37,450
What is the best combo of items to use at any given point in time?

189
00:13:38,560 --> 00:13:44,020
So if we break the problem down for each item in each potential amount of space left, it can exist.

190
00:13:44,020 --> 00:13:49,960
We noticed that there are some answers that can help us, some answers to some problems that can help

191
00:13:49,960 --> 00:13:52,030
us to other problems solve other problems.

192
00:13:52,600 --> 00:13:58,600
So an example is if I had three different items, I was told that a knapsack has capacity to an optimal

193
00:13:58,600 --> 00:14:02,410
solution of for profit when using item number one.

194
00:14:03,630 --> 00:14:10,350
I know that if I was to use a different item, so not item number one, but same capacity, same current

195
00:14:10,350 --> 00:14:17,580
capacity, I could use this answer of, hey, they said four was the best and I could compare it to

196
00:14:17,580 --> 00:14:20,820
what that would look like if I use the new item instead.

197
00:14:21,060 --> 00:14:27,630
So if I got a better profit from using item, let's say two instead of item one, then I could just

198
00:14:27,630 --> 00:14:32,010
add it to the knapsack and move on, and I could use that as my solution to this new sub problem.

199
00:14:32,400 --> 00:14:34,320
Otherwise, what I could do is, I could say.

200
00:14:35,320 --> 00:14:40,300
Hey, it's not better, so what I'm going to do is just use that answer that I already had like it already

201
00:14:40,300 --> 00:14:41,920
said for profit is the best.

202
00:14:42,100 --> 00:14:46,810
If I was to not use, I one use item two for the same capacity.

203
00:14:47,260 --> 00:14:48,340
And it wasn't as good.

204
00:14:49,030 --> 00:14:50,860
Then I'm going to say, you know what?

205
00:14:51,190 --> 00:14:55,630
Let's just go with what was already said then, because this is the best with like.

206
00:14:57,440 --> 00:15:04,280
You know, so far to what we figured out so far is that Max profit is for so let's just roll with that

207
00:15:04,280 --> 00:15:05,600
and then go try another item.

208
00:15:06,290 --> 00:15:08,460
So I use that solution to help me.

209
00:15:08,510 --> 00:15:13,850
It's already been calculated so I can grab that and kind of roll with it so we can kind of see how the

210
00:15:13,850 --> 00:15:18,860
optimal sub problem property is present, because that's a problem was already useful to us the answer

211
00:15:18,860 --> 00:15:22,640
of for maximum profit when we consider that item one.

212
00:15:22,910 --> 00:15:24,080
But what about repetition?

213
00:15:24,950 --> 00:15:27,530
Honestly, it's kind of the same thing what we've already described.

214
00:15:27,530 --> 00:15:33,560
So we're repeating the question of what is the most profit for X amount of space left in the knapsack?

215
00:15:33,590 --> 00:15:35,120
We're doing that over and over again.

216
00:15:36,590 --> 00:15:42,350
So the item that we're referring to for its problem is not what makes it a unique said problem.

217
00:15:42,350 --> 00:15:48,050
It's really the question of how much profit given remaining space, that is the same problem.

218
00:15:49,070 --> 00:15:51,520
So that's what's getting repeated over and over again.

219
00:15:51,530 --> 00:15:57,980
And it would be nice if we already had an answer that we could just go look up if we didn't find something.

220
00:15:57,980 --> 00:16:00,290
Let's say we add a new item to our knapsack.

221
00:16:01,690 --> 00:16:04,030
And for a given capacity and.

222
00:16:05,450 --> 00:16:06,740
It gives us a value, right?

223
00:16:06,830 --> 00:16:11,900
It gives us this maximum value now when we add it, and what we could do is kind of compare it to something

224
00:16:11,900 --> 00:16:14,270
that's already been calculated for that amount of space.

225
00:16:15,140 --> 00:16:19,430
And if it's not as good as what was already calculated, then let's just take that thing that was already

226
00:16:19,430 --> 00:16:21,200
calculated and move on to the next thing.

227
00:16:21,680 --> 00:16:27,410
Or if it's better, then hey, let's updated to now this is the best amount, and then let's move on

228
00:16:27,410 --> 00:16:28,130
to the next thing.

229
00:16:28,370 --> 00:16:29,900
So that's kind of what we're talking about here.

230
00:16:31,730 --> 00:16:33,290
And we choose not to use an item.

231
00:16:33,290 --> 00:16:38,600
We grab the already calculated max profit from X amount of space left some problem.

232
00:16:39,780 --> 00:16:42,810
And then we go on to concerning the next item, otherwise we update.

233
00:16:43,500 --> 00:16:46,650
So this is a little confusing with words, especially if you're a visual learner.

234
00:16:46,740 --> 00:16:49,380
So of course, we're going to visualize this now, right?

235
00:16:49,800 --> 00:16:55,560
And we're going to do it with a table because most dynamic programming problems are using a table.

236
00:16:56,580 --> 00:17:05,220
So I haven't used the same exact example, but I kind of simplified it to just make the explanation

237
00:17:05,220 --> 00:17:07,680
a little more succinct and more simple here.

238
00:17:07,710 --> 00:17:13,950
So what we have is columns are representing a current capacity of the knapsack.

239
00:17:14,760 --> 00:17:19,680
And this would be like the overall capacity that we started out with.

240
00:17:19,920 --> 00:17:26,100
For our question, like so when the problem started out, if someone told us knapsack is capacity for.

241
00:17:27,130 --> 00:17:33,520
That's this number here, and we're going from zero up to that number four columns in our table and

242
00:17:33,520 --> 00:17:36,040
the rows are the items that we're considering.

243
00:17:36,790 --> 00:17:44,260
So the sub problems we're solving here are like given a specific capacity, current capacity.

244
00:17:45,230 --> 00:17:50,720
You know, what is the best value we can get using a given item?

245
00:17:52,050 --> 00:17:59,580
And you notice as we work down or like to these other items, we could have already has some like items

246
00:17:59,580 --> 00:18:00,110
in here.

247
00:18:00,120 --> 00:18:06,660
So this grid helps us consider things that have already been calculated for specific items to know if

248
00:18:06,660 --> 00:18:08,370
we were to add a new item.

249
00:18:09,180 --> 00:18:12,000
Would it really give us a better answer or not?

250
00:18:12,690 --> 00:18:16,740
So that's kind of how we're going to move through this and fill these cells out and where you go from

251
00:18:17,190 --> 00:18:19,500
upper left to bottom right.

252
00:18:22,170 --> 00:18:24,240
So let's start out right now with item one.

253
00:18:25,530 --> 00:18:30,960
We noticed that item one has a weight of three and a value of three.

254
00:18:32,330 --> 00:18:38,570
So how what would we get, what's the max value we could get using it with a knapsack of capacity?

255
00:18:39,190 --> 00:18:44,380
Zero using this item, one with the capacity zero, what capacity is zero?

256
00:18:44,390 --> 00:18:46,420
That's kind of weird, right?

257
00:18:46,430 --> 00:18:47,180
Because.

258
00:18:48,310 --> 00:18:50,950
Honestly, it's like not even having a knapsack at all.

259
00:18:51,990 --> 00:18:57,570
You can't put anything if you don't have a knapsack or there's no knapsack to put anything in his capacity,

260
00:18:57,570 --> 00:18:59,790
zero is basically like an empty net or not empty.

261
00:18:59,790 --> 00:19:02,340
It's just like a non-existent knapsack.

262
00:19:02,910 --> 00:19:04,980
So we're going to say that we can't get anything out of that.

263
00:19:05,310 --> 00:19:06,450
So value is zero.

264
00:19:08,070 --> 00:19:11,890
It's actually same thing for this to capacity is one.

265
00:19:12,240 --> 00:19:14,970
But we cannot fit this item.

266
00:19:14,970 --> 00:19:17,360
We only have one item right now to consider.

267
00:19:17,370 --> 00:19:19,320
We're just starting out on this first row.

268
00:19:20,280 --> 00:19:25,710
The weight of this first item is three, if we have a knapsack that only fits weight one.

269
00:19:26,160 --> 00:19:29,310
We cannot add this item, and so we're going to have to leave with an empty knapsack.

270
00:19:31,140 --> 00:19:32,340
Same thing for capacity.

271
00:19:32,340 --> 00:19:36,090
Two It still is in three now, though.

272
00:19:36,090 --> 00:19:40,800
Capacity three, we can fit our item in there, but since we're only considering one item, it's pretty

273
00:19:40,800 --> 00:19:41,250
easy.

274
00:19:41,260 --> 00:19:43,320
It's just going to be the value of that item, right?

275
00:19:43,770 --> 00:19:51,450
Same thing for a capacity for even though we have one extra space or weight, you know, left since

276
00:19:51,450 --> 00:19:57,030
we only have a weight three for this item, it doesn't really matter because we're only considering

277
00:19:57,030 --> 00:19:57,510
this item.

278
00:19:57,510 --> 00:20:02,070
So we just throw that one item in there, even though it has extra space and we leave with that and

279
00:20:02,070 --> 00:20:03,510
we only get three for our value.

280
00:20:05,490 --> 00:20:06,570
So let's go to the next row.

281
00:20:08,380 --> 00:20:11,260
Capacity zero, this is always going to be zero.

282
00:20:11,290 --> 00:20:16,600
Honestly, this whole column, because we can't fit anything in a capacity zero knapsack, so you can

283
00:20:16,600 --> 00:20:18,580
just always mark this as zero.

284
00:20:19,810 --> 00:20:27,080
So if this weight of item to is one, then if we go to one, we know we can add four.

285
00:20:28,180 --> 00:20:33,370
But here's the point in which we need to consider what we've calculated up to this point.

286
00:20:35,060 --> 00:20:42,740
So we're going to start using a formula and what we're going to do is say, OK, if I am to add this

287
00:20:42,740 --> 00:20:43,400
item.

288
00:20:46,330 --> 00:20:50,740
I want to see basically what?

289
00:20:51,870 --> 00:20:57,030
I like what my previous best capacity was.

290
00:20:58,410 --> 00:21:03,600
And I want to see what it would be like to add this new item in.

291
00:21:05,170 --> 00:21:10,570
And so what I want to do is look up here.

292
00:21:12,190 --> 00:21:14,800
In this same column for capacity is one.

293
00:21:15,880 --> 00:21:23,470
This cell right above me is going to have the answer of when I am not considering this item.

294
00:21:24,460 --> 00:21:27,100
This was the best value I could get.

295
00:21:28,250 --> 00:21:31,700
If I am going to consider this adding this item, what I need to do.

296
00:21:32,780 --> 00:21:34,820
It's not just look at the items of value.

297
00:21:35,840 --> 00:21:39,890
I actually need to think of what it would be like to.

298
00:21:42,440 --> 00:21:44,720
Have this item in my knapsack.

299
00:21:46,400 --> 00:21:52,940
And have it fit based on its weight, so what I need to do is actually since the weight is one I go

300
00:21:52,940 --> 00:21:55,970
back up to when I just had item one.

301
00:21:57,070 --> 00:22:03,970
And I need to go over one because I need to get rid of some of the capacity.

302
00:22:05,520 --> 00:22:06,060
So.

303
00:22:07,200 --> 00:22:12,580
And basically what you're doing is you're subtracting the weight from the certain from the specific

304
00:22:12,820 --> 00:22:13,840
capacity here.

305
00:22:15,330 --> 00:22:24,430
So it's kind of like, you know, freeing up the space or whatever, so what we would do is go up one

306
00:22:24,450 --> 00:22:28,230
and over one to basically look for what's here.

307
00:22:28,710 --> 00:22:38,070
And that would be the value in which we would add our new items value to in the some of that, we would

308
00:22:38,070 --> 00:22:42,900
then compare to what the best was previously without considering this item.

309
00:22:43,950 --> 00:22:45,060
So that's what we're going to do.

310
00:22:48,560 --> 00:22:50,390
So this is there's some problem here.

311
00:22:50,660 --> 00:22:52,940
If Rosie and columnist Jay.

312
00:22:54,310 --> 00:23:02,500
Then the sub problem that we have to look at to be able to use to calculate our new answer is.

313
00:23:03,620 --> 00:23:04,670
At the position.

314
00:23:05,610 --> 00:23:07,050
Table I.

315
00:23:07,560 --> 00:23:10,830
Minus one, which is the item minus one.

316
00:23:11,370 --> 00:23:19,110
So we're going to go up one by arrow and then it's going to be J, which is columns which are columns

317
00:23:19,110 --> 00:23:19,350
J.

318
00:23:19,350 --> 00:23:21,750
J minus II's weight.

319
00:23:21,760 --> 00:23:26,430
I remember I as rose, so I weight is one.

320
00:23:26,850 --> 00:23:29,130
So we're going to go over one column.

321
00:23:30,600 --> 00:23:36,720
So up to the previous row, to the left by whatever the weight is.

322
00:23:37,780 --> 00:23:38,390
And columns.

323
00:23:39,370 --> 00:23:40,870
So we take this zero.

324
00:23:41,860 --> 00:23:44,110
We add this four to it, zero plus four.

325
00:23:44,830 --> 00:23:47,740
And then we compare it to this value right here.

326
00:23:48,340 --> 00:23:51,790
And four is greater than this zero right here.

327
00:23:52,090 --> 00:23:54,790
So therefore, the thing we're going to put here is for.

328
00:23:56,800 --> 00:24:00,220
And we're going to keep going through our table and updating it in this fashion.

329
00:24:01,550 --> 00:24:09,500
If it's not greater than or if the item cannot fit at all, then we'll just bring this value that was

330
00:24:09,500 --> 00:24:11,840
previously the best down into our new sale.

331
00:24:12,860 --> 00:24:19,310
So for example, if the weight was exceeding this, then we would just bring zero down if the weight

332
00:24:19,310 --> 00:24:19,990
was too big.

333
00:24:20,020 --> 00:24:25,880
We can't even fit it whatsoever just because by default, the item is just too big to fit in the knapsack.

334
00:24:26,180 --> 00:24:27,410
We would just bring this down.

335
00:24:27,980 --> 00:24:33,950
Same thing if we calculated by adding this to our value and we realize that this number was better,

336
00:24:33,950 --> 00:24:36,590
it was bigger than we would also just bring that down.

337
00:24:37,460 --> 00:24:43,310
But since that wasn't the case, are some from this number, and this number is what we ended up putting

338
00:24:43,310 --> 00:24:43,490
here.

339
00:24:44,840 --> 00:24:48,290
I just want to make sure everyone's on the same page before we move forward.

340
00:24:49,100 --> 00:24:54,890
So so we're going to keep using this formula for all the cells in the table if the item can be used.

341
00:24:55,100 --> 00:24:59,840
We will use what we did right there with the addition of these two and put it down.

342
00:25:01,720 --> 00:25:02,920
So let's check this one out.

343
00:25:03,670 --> 00:25:05,860
So we look above, we got zero here.

344
00:25:07,930 --> 00:25:15,130
And what we're going to do is actually, since the wait is one, we go up and over one and we add four

345
00:25:15,130 --> 00:25:17,380
to zero, that's four, right?

346
00:25:18,850 --> 00:25:20,220
That's a greater than zero.

347
00:25:20,230 --> 00:25:21,210
So we add four here.

348
00:25:21,670 --> 00:25:23,230
It's greater than this zero.

349
00:25:25,060 --> 00:25:25,960
Same thing here.

350
00:25:26,890 --> 00:25:30,340
When you're up and over one, this is zero plus four is four.

351
00:25:31,180 --> 00:25:32,710
Four is bigger than three.

352
00:25:32,710 --> 00:25:33,850
So we put a four there.

353
00:25:34,510 --> 00:25:38,790
And then this last one's going to be the same thing.

354
00:25:38,800 --> 00:25:43,420
But what we will do is I get a different number because we're going to add four to three.

355
00:25:43,840 --> 00:25:48,310
So same thing the weights one, we go up to our last row, we go over one to the left.

356
00:25:48,640 --> 00:25:49,990
We have four plus three.

357
00:25:49,990 --> 00:25:52,270
That's seven seven is bigger than three.

358
00:25:52,270 --> 00:25:56,500
So we put a seven here, OK?

359
00:25:56,500 --> 00:25:58,430
And we said we're always going for zero in this column, right?

360
00:25:58,450 --> 00:26:01,300
Because we can't say anything in a knapsack of capacity zero.

361
00:26:02,840 --> 00:26:08,120
And capacity one, we're just going to bring down because you notice that the wait is too, so we cannot

362
00:26:08,120 --> 00:26:14,270
consider putting this item in just whatsoever since the wait is bigger than this capacity column.

363
00:26:14,270 --> 00:26:18,830
So we'll just bring the last best value down to here.

364
00:26:19,100 --> 00:26:20,330
So for goes down to here.

365
00:26:22,250 --> 00:26:26,980
But now, since capacity is too in our ways, too, we can now consider this item.

366
00:26:26,990 --> 00:26:33,770
So what we will do is since the weight is to wear after we go up, we're going to go over to this time

367
00:26:34,100 --> 00:26:36,080
and we're going to add our value to this.

368
00:26:36,080 --> 00:26:37,850
So that's five zero five.

369
00:26:37,850 --> 00:26:39,140
That's better than four, right?

370
00:26:39,500 --> 00:26:40,610
So we'll put five there.

371
00:26:42,050 --> 00:26:46,940
Same thing here will go up and over to five plus four is nine nine is better than four.

372
00:26:46,940 --> 00:26:47,960
So we and that there.

373
00:26:50,600 --> 00:26:56,150
Five plus four is nine, that's better than seven, so we had a nine there, and now I'm just going

374
00:26:56,150 --> 00:26:58,130
to fill out for this next item.

375
00:26:58,880 --> 00:27:00,530
We noticed we have capacity.

376
00:27:00,800 --> 00:27:01,130
Sorry.

377
00:27:01,310 --> 00:27:05,700
We have our weight is four, so we know we're not going to be able to use any of the.

378
00:27:05,720 --> 00:27:11,930
We're not going to be able to like, consider adding this item for any of these because the knapsack

379
00:27:11,930 --> 00:27:15,890
capacity is of all these columns is less than our weight of the item.

380
00:27:16,190 --> 00:27:23,780
So we're just going to bring all these values down because this is going to be the same optimal value

381
00:27:24,020 --> 00:27:26,360
at this point since we can consider the item.

382
00:27:27,740 --> 00:27:29,900
So that will lead us to figure out this one right here.

383
00:27:30,440 --> 00:27:33,960
So we have value of six and a weight of four.

384
00:27:34,580 --> 00:27:38,600
So we would go up and then over four one two three four.

385
00:27:39,980 --> 00:27:43,060
So six plus zero six is six better than nine.

386
00:27:43,070 --> 00:27:44,330
It's not better than nine.

387
00:27:44,330 --> 00:27:45,920
So we're just going to bring the nine down.

388
00:27:47,000 --> 00:27:54,440
And this actually gives us our final answer the the final answer to the best value you can get.

389
00:27:55,410 --> 00:28:01,410
In your knapsack, given all of this input, it's going to be in the bottom right hand corner of the

390
00:28:01,410 --> 00:28:01,860
table.

391
00:28:04,560 --> 00:28:09,120
Another interesting thing is that we can answer the other part of the question that we want to know.

392
00:28:09,150 --> 00:28:14,730
Well, we just calculated all this stuff, but we didn't necessarily like keep track of the items we

393
00:28:14,730 --> 00:28:15,320
were using.

394
00:28:15,330 --> 00:28:20,460
We might know what we really use just by memory of us thinking.

395
00:28:21,820 --> 00:28:26,380
About, you know, the fact that we didn't use this.

396
00:28:27,430 --> 00:28:32,740
You know, and instead use like we did use this one right, and we did use this one, but we can actually

397
00:28:32,740 --> 00:28:39,760
back trace to be able to figure out exactly what we used just by figuring out where we came from in

398
00:28:39,760 --> 00:28:43,810
the grid, like which cell did we end up using when we had the question mark here?

399
00:28:44,650 --> 00:28:45,520
So let's do that.

400
00:28:45,880 --> 00:28:47,920
So first of all, we do is look right above.

401
00:28:49,550 --> 00:28:51,620
Is this value above us less?

402
00:28:52,760 --> 00:28:56,090
If it's not less, then we didn't use it.

403
00:28:57,020 --> 00:29:01,790
So that means that we just brought this nine down and that's what we did, right?

404
00:29:01,790 --> 00:29:07,070
So we can just go back, we can go right back up to where we came from, which was we brought this nine

405
00:29:07,070 --> 00:29:07,490
down.

406
00:29:07,490 --> 00:29:08,630
So we're going to go up to it.

407
00:29:10,040 --> 00:29:11,000
Is this less?

408
00:29:11,120 --> 00:29:12,730
Yeah, this is less so.

409
00:29:12,740 --> 00:29:19,160
That means that we since the weight is too, we went up and looked over too, and we ended up using

410
00:29:19,160 --> 00:29:21,800
this and adding five to it to get our nine.

411
00:29:22,130 --> 00:29:25,940
So we were using this cell, so we'll now go over there.

412
00:29:27,290 --> 00:29:35,780
And since we used this item three, we would add that to like a list or something so we could keep track

413
00:29:35,780 --> 00:29:36,770
of the items we use.

414
00:29:36,810 --> 00:29:41,990
You know, since this was less and we realized that we used this and had five plus four is nine.

415
00:29:42,860 --> 00:29:45,320
Then we would add, we say, Hey, we did use item three.

416
00:29:45,320 --> 00:29:48,650
So we'll add that to some sort of container to keep track as we backtrace.

417
00:29:49,760 --> 00:29:50,720
So now we're here.

418
00:29:51,020 --> 00:29:52,100
Let's look one above.

419
00:29:52,940 --> 00:29:53,780
Is this less?

420
00:29:53,810 --> 00:29:58,670
Yes, it is less so if we were to go up and one over.

421
00:29:58,710 --> 00:30:00,050
That's what we ended up using.

422
00:30:00,050 --> 00:30:01,430
Was this cell right here?

423
00:30:01,640 --> 00:30:05,060
So we had four plus zero give gave us four.

424
00:30:06,500 --> 00:30:07,550
So we go here.

425
00:30:07,790 --> 00:30:13,310
And then at this point, I don't really have item zero represented on here because there is no real

426
00:30:13,310 --> 00:30:13,970
item to you.

427
00:30:13,970 --> 00:30:21,680
But in the actual implementation, you will probably have an item zero, just like you have a capacity

428
00:30:21,680 --> 00:30:26,360
zero, just because you'll use like a standard matrix or something to represent this.

429
00:30:26,360 --> 00:30:30,890
And that'll just be all zeroed out since you have an item zero.

430
00:30:31,010 --> 00:30:39,350
But once we hit that zero like items zero zero zero or column zero, we can just stop the bacteria.

431
00:30:39,380 --> 00:30:41,520
So at this point, we're pretty much done.

432
00:30:41,810 --> 00:30:46,580
We know that we used Item two and we use Item three because we kept track of this.

433
00:30:48,620 --> 00:30:49,640
So that's pretty much it.

434
00:30:49,820 --> 00:30:53,330
Now it's time to write some code, which I will do in the next lecture.

435
00:30:53,630 --> 00:31:00,590
And I also kind of point out the specific like mathematical representation of when we're choosing a

436
00:31:00,590 --> 00:31:03,800
max value because you can kind of right that in mathematical terms here.

437
00:31:03,800 --> 00:31:08,390
I just tried to explain it in some layman's terms, but I might write that as well.

438
00:31:08,390 --> 00:31:11,780
In addition to the code in the next lecture, some of you like to see that.

439
00:31:12,980 --> 00:31:17,540
OK, so with that, I will see you in the next lecture, which we will try and implement this dynamic

440
00:31:17,540 --> 00:31:19,370
programming algorithm.