1
00:00:00,380 --> 00:00:03,300
Discrete Optimization.
Welcome back.

2
00:00:03,300 --> 00:00:05,720
This is dynamic programming, okay?

3
00:00:05,720 --> 00:00:07,440
So this is the first lecture where we're

4
00:00:07,440 --> 00:00:09,880
really going to go into some technical
details.

5
00:00:09,880 --> 00:00:13,940
So what we're going to do is basically
show you how you can get the best possible

6
00:00:13,940 --> 00:00:16,070
solution to the knapsack problem and we're
going

7
00:00:16,070 --> 00:00:19,000
to use this first technique which is
Dynamic programming.

8
00:00:19,000 --> 00:00:22,600
So in this class, what we are doing is
giving you a lot of hats, okay?

9
00:00:22,600 --> 00:00:23,920
Optimization hats.

10
00:00:23,920 --> 00:00:25,420
And these are different techniques that
you

11
00:00:25,420 --> 00:00:28,710
can use for solving optimization problems.

12
00:00:28,710 --> 00:00:31,710
And we will tell you, really, which one is
good and which one is not good.

13
00:00:31,710 --> 00:00:33,120
Actually, we don't really know.

14
00:00:33,120 --> 00:00:36,340
But they will give you tools to actually
look at these problems and try to

15
00:00:36,340 --> 00:00:37,650
solve them, and the first one that i'm

16
00:00:37,650 --> 00:00:40,130
going to talk about today is dynamic
programming.

17
00:00:40,130 --> 00:00:43,040
And dynamic programming is a very widely
used technique, okay.

18
00:00:43,040 --> 00:00:45,880
So when it works, it works really well and

19
00:00:45,880 --> 00:00:48,210
for various classes of problems it works
very well.

20
00:00:48,210 --> 00:00:50,620
Particular example is computation on
biology, a lot

21
00:00:50,620 --> 00:00:51,970
of the sequencing problems can be

22
00:00:51,970 --> 00:00:54,560
solved using dynamic programming, but
sometimes it

23
00:00:54,560 --> 00:00:58,580
doesn't work at all and we'll try to give
you intuition why okay?

24
00:00:58,580 --> 00:01:02,990
And, and, but this is a very useful
technique when it works as I said, okay?

25
00:01:02,990 --> 00:01:07,970
So the basic principle is, is very simple.
It's a divide and conquer approach, okay?

26
00:01:07,970 --> 00:01:10,200
You know, you're going to split the
problems in different parts.

27
00:01:10,200 --> 00:01:11,980
But the really important thing is

28
00:01:11,980 --> 00:01:14,790
that it's a bottom-up computation
technique, okay?

29
00:01:14,790 --> 00:01:15,620
So if you can do

30
00:01:15,620 --> 00:01:19,160
that in a top-down divide and conquer, in
a top-down or bottom-up technique.

31
00:01:19,160 --> 00:01:21,570
Okay, and dynamic programming is about
bottom-up.

32
00:01:21,570 --> 00:01:26,070
We'll see a top-down technique later on,
also on the knapsack problem, okay?

33
00:01:26,070 --> 00:01:28,765
So, let's talk about dynamic programming,
and

34
00:01:28,765 --> 00:01:29,480
once again I'm going to assume that the

35
00:01:29,480 --> 00:01:34,600
same conventions that we use when we
talked about the modeling of the knapsack.

36
00:01:34,600 --> 00:01:36,950
So, we have a set of item capital I and

37
00:01:36,950 --> 00:01:39,980
these items are going to be denoted from 1
to n, okay?

38
00:01:39,980 --> 00:01:40,850
So, these are the various

39
00:01:40,850 --> 00:01:44,390
item that I can pick up.
They have a name which is 1 to n.

40
00:01:44,390 --> 00:01:47,755
And then I'm going to make another
convention which is this O(k,j), okay?

41
00:01:47,755 --> 00:01:52,080
And O(k,j) is essentially The value of the
optimal

42
00:01:52,080 --> 00:01:54,950
knapsack, if the capacity of the knapsack
is k.

43
00:01:54,950 --> 00:01:58,160
And you can select item from one to j.
Okay?

44
00:01:58,160 --> 00:02:01,860
So this is kind of a set problem and we're
going to build from it, okay?

45
00:02:01,860 --> 00:02:05,810
The way you can formalize it is exactly
the way I formalized the knapsack, right?

46
00:02:05,810 --> 00:02:10,110
But at this time only we look at the j
Under the first j item.

47
00:02:10,110 --> 00:02:10,600
Okay?

48
00:02:10,600 --> 00:02:12,620
So, in the sense, you know, look at the
problem here.

49
00:02:12,620 --> 00:02:14,800
You know, you see, you see that, you, you
see that

50
00:02:14,800 --> 00:02:18,040
I'm only, I'm not using n there, I'm
basically using j.

51
00:02:18,040 --> 00:02:18,750
Okay?

52
00:02:18,750 --> 00:02:21,370
And obviously what we are interested in is
solving the

53
00:02:21,370 --> 00:02:24,530
problem where we use the full capacity of
the knapsack, capital

54
00:02:24,530 --> 00:02:27,100
K, and where we use all the item, but we

55
00:02:27,100 --> 00:02:30,439
will be basically using this problem as,
as a building block.

56
00:02:32,160 --> 00:02:35,380
So, what I'm going to do is basically com,
be completely outrageous.

57
00:02:35,380 --> 00:02:39,180
I'm going to assume that I can solve all
the sub problems

58
00:02:39,180 --> 00:02:43,220
for a capacity k, any capacity k and j
minus one item.

59
00:02:43,220 --> 00:02:44,740
So, I have this oracle, okay?

60
00:02:44,740 --> 00:02:47,920
Delphi oracle that's going to tell me the
optimal value

61
00:02:47,920 --> 00:02:50,180
for these two, fo, for all these things,
okay?

62
00:02:50,180 --> 00:02:53,560
I'm assume that I'm basically given this,
okay?

63
00:02:53,560 --> 00:02:55,070
So that's the oracle that I have.

64
00:02:55,070 --> 00:02:57,080
And then I can query.
I can always ask: Ooo,

65
00:02:57,080 --> 00:03:02,920
what is the value for the j minus one item
for this particular capacity.

66
00:03:02,920 --> 00:03:05,120
And I can query this oracle and get this
value.

67
00:03:05,120 --> 00:03:05,810
Okay?

68
00:03:05,810 --> 00:03:11,425
So the next, usually what I want to do now
is add one tiny little item, okay?

69
00:03:11,425 --> 00:03:12,260
O(k,j).

70
00:03:12,260 --> 00:03:17,400
So I know how to compute O O(k,j-1) for
any value of

71
00:03:17,400 --> 00:03:22,160
k, and what I want to do now is compute
O(k,j) for all

72
00:03:22,160 --> 00:03:23,790
the values of k as well, okay?

73
00:03:23,790 --> 00:03:26,610
I'm just considering one item, and you're
going to see

74
00:03:26,610 --> 00:03:28,320
it's pretty simple what you have to do,
okay?

75
00:03:28,320 --> 00:03:32,040
So the first thing you have to do Is to
find out if that particular

76
00:03:32,040 --> 00:03:34,200
item, if you have a capacity k, if

77
00:03:34,200 --> 00:03:36,480
that particular item can fit inside and
outside.

78
00:03:36,480 --> 00:03:39,330
If it's weight is lower down than the
capacity k.

79
00:03:39,330 --> 00:03:41,260
If this is the case, then there are two

80
00:03:41,260 --> 00:03:43,260
other, there are two cases that you need
to consider.

81
00:03:43,260 --> 00:03:47,260
The first one is, whether you are right to
be selecting the item or not.

82
00:03:47,260 --> 00:03:49,220
Okay.
If whether you are selecting the item.

83
00:03:49,220 --> 00:03:52,600
If you don't select the item, the value
that you get is simply

84
00:03:52,600 --> 00:03:56,770
the value of the item with the same
capacity and j minus 1 item.

85
00:03:56,770 --> 00:03:58,640
Okay?
And we have the O record to compute that.

86
00:03:58,640 --> 00:03:59,990
That's the value that you see there.

87
00:03:59,990 --> 00:04:00,550
Okay?

88
00:04:00,550 --> 00:04:03,110
So if the item fits and we decide not to
select

89
00:04:03,110 --> 00:04:07,030
it, what you get is Is basically O(k,j)
minus 1, okay?

90
00:04:07,030 --> 00:04:08,810
Now, you can select the item.

91
00:04:08,810 --> 00:04:09,370
Okay?

92
00:04:09,370 --> 00:04:11,990
Because we know that it fits and in that
particular case,

93
00:04:11,990 --> 00:04:14,100
what is the value that you get?
Okay?

94
00:04:14,100 --> 00:04:16,370
You get obviously the value of the item
because you put

95
00:04:16,370 --> 00:04:19,580
it inside the knapsack and then you get
the value, the optimal

96
00:04:19,580 --> 00:04:23,450
value that you can get by using the g
minus 1 item

97
00:04:23,450 --> 00:04:27,560
and the capacity which is obtained by
removing the weight from k.

98
00:04:27,560 --> 00:04:30,090
Okay the weight of the item you just
selected and

99
00:04:30,090 --> 00:04:32,560
as this expression that you say, that you
see here.

100
00:04:32,560 --> 00:04:37,500
Is v j plus the value of a k w,

101
00:04:37,500 --> 00:04:40,640
you know, let me, let me start out again.

102
00:04:40,640 --> 00:04:42,810
It's the value of vj which is the value of

103
00:04:42,810 --> 00:04:46,840
the item, and then o, you know, call this
orecorsursivly

104
00:04:46,840 --> 00:04:50,770
with the value of the capacity k minus the
weight

105
00:04:50,770 --> 00:04:54,380
of the item, wj, and then obviously j
minus one item.

106
00:04:54,380 --> 00:04:57,790
And so these are the two things that you
can do if the item fits in the knapsack.

107
00:04:57,790 --> 00:05:00,380
If the item doesn't fit in the knapsack,
what do you have?

108
00:05:00,380 --> 00:05:02,668
Well, you are, you are only left with the
value

109
00:05:02,668 --> 00:05:05,920
of the j minus one item and the same
capacity k.

110
00:05:05,920 --> 00:05:06,430
Okay?

111
00:05:06,430 --> 00:05:10,520
So we can build this beautiful recurrence
relationship here, okay?

112
00:05:10,520 --> 00:05:13,820
Which consider the capacity k and j item
and you

113
00:05:13,820 --> 00:05:17,220
basically re-express it as a maximum
between these two value.

114
00:05:17,220 --> 00:05:19,490
If the act, if the item can fit inside

115
00:05:19,490 --> 00:05:22,220
the knapsack, and otherwise it's simply
the same val,

116
00:05:22,220 --> 00:05:25,370
the, the same the, the, is basically the
same

117
00:05:25,370 --> 00:05:27,760
value as you would get If you use only j

118
00:05:27,760 --> 00:05:29,390
minus 1 item, okay?

119
00:05:29,390 --> 00:05:33,030
So you have this beautiful recurrence
relationship, finding the best case when

120
00:05:33,030 --> 00:05:36,020
the item can fit whether you select or you
don't select the item.

121
00:05:36,020 --> 00:05:38,270
Or if the item doesn't fit you just, you
know, end the

122
00:05:38,270 --> 00:05:41,130
value that you could do with the j minus 1
item, okay?

123
00:05:41,130 --> 00:05:43,510
And of course you have to start from
where, if the

124
00:05:43,510 --> 00:05:46,330
capacity is zero There is no item that you
can put

125
00:05:46,330 --> 00:05:48,880
in the [UNKNOWN] and what I am basically
climbing is that

126
00:05:48,880 --> 00:05:53,610
if you have these swings okay, you can
compute the optimal value

127
00:05:53,610 --> 00:05:56,800
of the [UNKNOWN] and which item you need
to select okay.

128
00:05:56,800 --> 00:05:57,780
How do you do that?

129
00:05:57,780 --> 00:05:58,890
Well let me show you.

130
00:05:58,890 --> 00:06:01,440
This is a very simple c program or Python

131
00:06:01,440 --> 00:06:03,540
program, you can derive the same thing in
Python to

132
00:06:03,540 --> 00:06:06,150
do actually that because you know where
computer science

133
00:06:06,150 --> 00:06:09,510
is just computing this Oracle for you for
free okay?

134
00:06:09,510 --> 00:06:14,060
So you see basically O(k,j), okay and
that's the function that we're defining

135
00:06:14,060 --> 00:06:18,510
here obviously if j is equal to zero there
are no item okay?

136
00:06:18,510 --> 00:06:22,180
There is nothing you can do, therefore the
value is zero.

137
00:06:22,180 --> 00:06:25,820
Otherwise you look at the item j and
whether it fits or not

138
00:06:25,820 --> 00:06:29,760
in, in the knapsack, okay so you have the
capacity k, you have w

139
00:06:29,760 --> 00:06:32,540
j, if it fits in the knapsack what you
have to do the

140
00:06:32,540 --> 00:06:36,040
optimum value of the knapsack is going to
be the max of this expression.

141
00:06:36,040 --> 00:06:36,280
Okay?

142
00:06:36,280 --> 00:06:39,760
And once again this consider the two cases
that I have discussed before, and

143
00:06:39,760 --> 00:06:41,815
otherwise if it doesn't fit you simply

144
00:06:41,815 --> 00:06:43,950
come, you know, call the function
recursively.

145
00:06:43,950 --> 00:06:45,420
That's the oracle, right?

146
00:06:45,420 --> 00:06:48,660
With one fewer item in the same capacity,
okay?

147
00:06:48,660 --> 00:06:54,300
That program is actually computing the
optimal value for the knapsack, okay?

148
00:06:54,300 --> 00:06:58,440
Now one question that I have for you is
that, is this actually efficient?

149
00:06:58,440 --> 00:06:59,030
Okay?

150
00:06:59,030 --> 00:07:01,860
Can you tell me how efficient this
algorithm is?

151
00:07:01,860 --> 00:07:02,060
Okay?

152
00:07:02,060 --> 00:07:03,910
And let me use an analogy here.

153
00:07:03,910 --> 00:07:05,460
This is, what I am going to show you here

154
00:07:05,460 --> 00:07:09,160
is a program for computing Fibonacci
numbers and it's basically

155
00:07:09,160 --> 00:07:11,470
the same structure, a little bit simpler,
than

156
00:07:11,470 --> 00:07:13,780
what I've shown you for the knapsack
problem, okay?

157
00:07:13,780 --> 00:07:18,150
If you want to compute a value of the
fibona, the fibonacci number of n, Okay?

158
00:07:18,150 --> 00:07:20,740
if n is equal to one Okay, the value is

159
00:07:20,740 --> 00:07:24,400
one, and otherwise if the value that you
obtain by computing

160
00:07:24,400 --> 00:07:27,070
the Fibonacci of n minus one, then minus
two and

161
00:07:27,070 --> 00:07:30,010
then adding that to the Fibonacci of n
minus one Okay.

162
00:07:30,010 --> 00:07:32,330
That's how you can compute Fibonacci
number, and

163
00:07:32,330 --> 00:07:34,120
I have the same question for you right,

164
00:07:34,120 --> 00:07:37,620
is this efficient or not Okay, and what
you can see here

165
00:07:37,620 --> 00:07:40,190
is that okay, so if you want to compute
when you look at

166
00:07:40,190 --> 00:07:43,690
this one, the value of Fibonacci n minus
one What will you have,

167
00:07:43,690 --> 00:07:46,470
what, what do you have to do to actually
compute that value, right?

168
00:07:46,470 --> 00:07:49,380
So you're going to compute this function
and you're going to compute Fibonacci

169
00:07:49,380 --> 00:07:52,100
of n minus 2 and n minus 3, but you just

170
00:07:52,100 --> 00:07:55,450
have computed Fibonacci n minus 2 and for
computing that you

171
00:07:55,450 --> 00:07:58,710
have computed the Fibonacci of n minus 3
and n minus 4.

172
00:07:58,710 --> 00:07:58,950
So yeah,

173
00:07:58,950 --> 00:08:02,990
basically, we are computing many, many,
many times the same values, okay?

174
00:08:02,990 --> 00:08:06,850
So this program is actually very, very,
very inefficient, okay?

175
00:08:06,850 --> 00:08:08,980
You never want to use anything like that,
okay?

176
00:08:08,980 --> 00:08:09,590
And why?

177
00:08:09,590 --> 00:08:11,970
Because in this particular case, it's
top-down

178
00:08:11,970 --> 00:08:13,670
and we are not doing anything fancy.

179
00:08:13,670 --> 00:08:14,030
Okay?

180
00:08:14,030 --> 00:08:16,490
So what I'm going to do is take the
exactly the

181
00:08:16,490 --> 00:08:20,200
opposite approach and we're going to do a
bottom up computation.

182
00:08:20,200 --> 00:08:20,540
Okay.

183
00:08:20,540 --> 00:08:22,100
So we're going to start with zero item.

184
00:08:22,100 --> 00:08:24,050
And that's what dynamic programming does.
Right?

185
00:08:24,050 --> 00:08:25,490
We start with zero item.

186
00:08:25,490 --> 00:08:29,020
And then, as I've shown you before we're
going put one more item and

187
00:08:29,020 --> 00:08:32,740
then two more items and so on until we
have selected all the items.

188
00:08:32,740 --> 00:08:33,390
Okay.

189
00:08:33,390 --> 00:08:35,290
So in a sense, look at this program here.

190
00:08:35,290 --> 00:08:37,860
This is the program that I'm going to use
in the next couple of slides.

191
00:08:37,860 --> 00:08:39,850
The first thing we going to do is oh we
going to

192
00:08:39,850 --> 00:08:42,460
look at what you can do with one, with
zero item.

193
00:08:42,460 --> 00:08:45,900
Then one item, and then two item, and then
three items.

194
00:08:45,900 --> 00:08:47,740
That's what we are trying to do here,
okay?

195
00:08:47,740 --> 00:08:49,360
We are going to solve these very simple

196
00:08:49,360 --> 00:08:50,010
sub problems.

197
00:08:50,010 --> 00:08:52,750
They are very simple and then we going to
build on top

198
00:08:52,750 --> 00:08:55,180
of them by adding one more item at a time,
okay?

199
00:08:55,180 --> 00:08:57,370
And you going to see, it's beautiful.

200
00:08:57,370 --> 00:08:59,250
Okay, so this is, and so, when you

201
00:08:59,250 --> 00:09:01,240
think about dynamic programming, you can,
you know, a

202
00:09:01,240 --> 00:09:03,070
lot of people think about tables, and I'm
going to

203
00:09:03,070 --> 00:09:06,230
show you the table intuition of dynamic
programming, okay?

204
00:09:06,230 --> 00:09:07,960
So you start with zero items.

205
00:09:07,960 --> 00:09:11,790
How much value can you get?
If you have 0 item, okay?

206
00:09:11,790 --> 00:09:14,390
The value that you get is 0, right?
So, there is nothing to

207
00:09:14,390 --> 00:09:15,280
take, okay?

208
00:09:15,280 --> 00:09:18,700
Now, we are looking at one item and assume
that this item

209
00:09:18,700 --> 00:09:22,340
as a value which is 5 and a capacity which
is 4.

210
00:09:22,340 --> 00:09:25,600
Until you have a capacity which exceed you
know, which exceeds

211
00:09:25,600 --> 00:09:29,050
Three, which exceeds 3, then there is
nothing you can get.

212
00:09:29,050 --> 00:09:30,610
You get no value.
Right?

213
00:09:30,610 --> 00:09:33,025
And then, essentially, as soon as the
capacity is

214
00:09:33,025 --> 00:09:34,440
4, you can get the value of the item.

215
00:09:34,440 --> 00:09:36,110
So this is amazingly simple, right?

216
00:09:36,110 --> 00:09:37,790
So we have one item, okay?

217
00:09:37,790 --> 00:09:39,700
Now let's look at what happens if we have
two items.

218
00:09:39,700 --> 00:09:44,730
To get a new item there, its value is 6
and its weight is 5.

219
00:09:44,730 --> 00:09:45,290
Okay?

220
00:09:45,290 --> 00:09:48,900
And once again until you get one item that
can fit in the knapsack you get nothing.

221
00:09:48,900 --> 00:09:50,980
So initially you get all these zeroes, and
then

222
00:09:50,980 --> 00:09:53,090
you get to the point where the capacity is
4.

223
00:09:53,090 --> 00:09:55,940
When the capacity is four you could get
the first item.

224
00:09:55,940 --> 00:10:00,970
So you get a five, okay?
When the capacity is 5 what do you get?

225
00:10:00,970 --> 00:10:03,980
Well you can select the second item which
is more valuable, okay?

226
00:10:03,980 --> 00:10:04,750
And that's what you get

227
00:10:04,750 --> 00:10:07,570
there, until the point where the two items
actually fit

228
00:10:07,570 --> 00:10:09,790
inside your knapsack and you get a value
of 11.

229
00:10:09,790 --> 00:10:12,420
Okay, so there's the second column, okay?

230
00:10:12,420 --> 00:10:13,550
So two items.

231
00:10:13,550 --> 00:10:17,450
Now we going to build on this second
column to actually build the case

232
00:10:17,450 --> 00:10:18,950
where there are three items, and this

233
00:10:18,950 --> 00:10:21,030
is where things start becoming more
interesting.

234
00:10:21,030 --> 00:10:24,140
You can see that the weight of this guy is
2, its value is 3, okay?

235
00:10:24,140 --> 00:10:26,310
So As long as we don't have at least

236
00:10:26,310 --> 00:10:28,670
two units of capacity, there is nothing
you can do.

237
00:10:28,670 --> 00:10:29,760
Okay?
When we have two

238
00:10:29,760 --> 00:10:33,665
units, we get basically, this item, the,
the third item,

239
00:10:33,665 --> 00:10:36,880
3, and this is where things really start
getting interesting.

240
00:10:36,880 --> 00:10:39,830
Okay, so in this particular case When you
have a capacity of

241
00:10:39,830 --> 00:10:42,860
4, there are two items that are fitting in
the knapsack, right?

242
00:10:42,860 --> 00:10:47,260
So this guy fits in the knapsack and you
can decide to take it or not to take it.

243
00:10:47,260 --> 00:10:49,200
If you don't take it, what happens?

244
00:10:49,200 --> 00:10:52,080
Well, you get the value that you would
have, that,

245
00:10:52,080 --> 00:10:54,770
that you, that you had when you select
only the first

246
00:10:54,770 --> 00:10:55,810
two item.
Okay?

247
00:10:55,810 --> 00:10:58,500
So, you know that you will at least get
value five, okay?

248
00:10:58,500 --> 00:10:59,870
Because if you don't do anything, you
don't

249
00:10:59,870 --> 00:11:02,510
select the item 3, you get the value 5.

250
00:11:02,510 --> 00:11:05,040
But now you have also the possibility of
selecting this guy.

251
00:11:05,040 --> 00:11:09,230
If you select this guy, you get its value
which is 3 in this particular case,

252
00:11:09,230 --> 00:11:11,440
but then you also have a non-empty you

253
00:11:11,440 --> 00:11:13,760
know, capacity for the knapsack in this
particular case.

254
00:11:15,270 --> 00:11:17,980
What do we get?
We get 1, okay?

255
00:11:17,980 --> 00:11:18,410
2, 2.

256
00:11:18,410 --> 00:11:20,028
We get 2.
But the value

257
00:11:20,028 --> 00:11:22,650
there, the value there for 2 is 0.
Okay?

258
00:11:22,650 --> 00:11:26,870
So basically you get the value 3 plus 0
which is there are 3 and therefore,

259
00:11:26,870 --> 00:11:30,020
it's better not to select the item and
that's what you get at that point okay?

260
00:11:30,020 --> 00:11:32,350
And this is the same for the next column.
You get 6.

261
00:11:32,350 --> 00:11:32,850
Okay?

262
00:11:32,850 --> 00:11:34,990
This is another case which is very
interesting okay?

263
00:11:34,990 --> 00:11:38,200
So you're looking at the capacity of the
knapsack which is six.

264
00:11:38,200 --> 00:11:38,770
Okay?

265
00:11:38,770 --> 00:11:41,090
And you can decide if you select the item
or not.

266
00:11:41,090 --> 00:11:44,970
If you don't select the item You get the
value which is on the left, which is 6,

267
00:11:44,970 --> 00:11:48,110
okay, but if you decide to select the
item, okay.

268
00:11:48,110 --> 00:11:51,270
So you get the value of the item which is
3 and then what

269
00:11:51,270 --> 00:11:54,310
you have is you still have a capacity of
the knapsack which, which is

270
00:11:54,310 --> 00:11:58,400
you know 4, and you can fid the first
item, which basically means in

271
00:11:58,400 --> 00:12:02,660
this particular case you have a value of 8
for the particle of knapsack, okay.

272
00:12:02,660 --> 00:12:05,510
So this is really, really interesting
though so essentially what

273
00:12:05,510 --> 00:12:07,382
you do is you have to look at two values.

274
00:12:07,382 --> 00:12:10,000
The value just on your left,

275
00:12:10,000 --> 00:12:12,480
and that's the value where you decide not
to take

276
00:12:12,480 --> 00:12:15,580
the item, or the value which is in the
previous column,

277
00:12:15,580 --> 00:12:18,740
but where you have removed the capacity of
the items that

278
00:12:18,740 --> 00:12:20,880
you, the, the, the weight of the item that
you get.

279
00:12:20,880 --> 00:12:23,740
You, you get another capacity for your
knapsack.

280
00:12:23,740 --> 00:12:25,650
And now you know that you have solved that

281
00:12:25,650 --> 00:12:28,200
particular problem, and you can use the
value, right?

282
00:12:28,200 --> 00:12:30,530
So this is what dynamic programming does.

283
00:12:30,530 --> 00:12:35,100
You recompute this new column, okay, based
only on the previous column and

284
00:12:35,100 --> 00:12:38,030
two values in that column.
Isn't that beautiful?

285
00:12:38,030 --> 00:12:39,820
Very, very simple, okay?

286
00:12:39,820 --> 00:12:42,250
Now, you can wonder, but, but where is the
optimal value

287
00:12:42,250 --> 00:12:46,065
of the knapsack and this is their, this is
my precious, right?

288
00:12:46,065 --> 00:12:49,330
11 is the optimal size of the knapsack.

289
00:12:49,330 --> 00:12:54,380
I know that this value here at the bottom
right corner is what I want.

290
00:12:54,380 --> 00:12:54,820
Okay?

291
00:12:54,820 --> 00:12:57,300
You're going to say, yeah, yeah, yeah, but
that's the value of the optimal knapsack.

292
00:12:57,300 --> 00:13:00,220
What is the optimal solution?
And I'm going to show you now how

293
00:13:00,220 --> 00:13:03,170
you can actually get that value of the
optimal solution.

294
00:13:03,170 --> 00:13:05,710
The only thing you've to do is trace back
for my

295
00:13:05,710 --> 00:13:09,610
precious until you get to the beginning of
the table, right.

296
00:13:09,610 --> 00:13:10,890
So what do you do with the following?

297
00:13:10,890 --> 00:13:13,620
You look at the value of the way you are
and

298
00:13:13,620 --> 00:13:18,890
then you look at the previous column just
on your left.

299
00:13:18,890 --> 00:13:19,430
Okay?

300
00:13:19,430 --> 00:13:21,600
If the values are the same what do you
know?

301
00:13:21,600 --> 00:13:23,950
You know that you haven't select the item,
okay?

302
00:13:23,950 --> 00:13:25,430
Because the value with one fewer

303
00:13:25,430 --> 00:13:26,940
item is the same, okay?

304
00:13:26,940 --> 00:13:29,300
So you know that the decision variable for

305
00:13:29,300 --> 00:13:33,190
that particular, the, for that particular
item is zero.

306
00:13:33,190 --> 00:13:35,540
You haven't selected that item, okay?

307
00:13:35,540 --> 00:13:37,360
Now you look at this value and you do the
same thing.

308
00:13:37,360 --> 00:13:39,040
Okay, so is this the same as that?

309
00:13:39,040 --> 00:13:40,050
No it's not.

310
00:13:40,050 --> 00:13:42,440
That basically mean that you selected item
two.

311
00:13:42,440 --> 00:13:45,720
You remove the weight of that item, you
get another capacity

312
00:13:45,720 --> 00:13:48,370
that you can use for the, you know, the
remaining items, okay?

313
00:13:48,370 --> 00:13:50,510
And you do the same here.
5, is it,

314
00:13:50,510 --> 00:13:51,810
is it the same as 0?
No.

315
00:13:51,810 --> 00:13:54,250
That basically means that you selected
that item.

316
00:13:54,250 --> 00:13:58,350
And so basically, at this point, you know
that you're selecting item one.

317
00:13:58,350 --> 00:14:01,500
In item two, okay, so that's the optimal
solution.

318
00:14:01,500 --> 00:14:04,680
And once again the only thing that you
have to do is take the bottom

319
00:14:04,680 --> 00:14:07,550
right corner and trace back inside your

320
00:14:07,550 --> 00:14:10,630
table and you have the optimal solution,
okay?

321
00:14:10,630 --> 00:14:13,400
That's the beauty of dynamic programming,
your computer is stable

322
00:14:13,400 --> 00:14:15,520
and then you trace back and you get the
optimum

323
00:14:15,520 --> 00:14:16,750
value, okay?

324
00:14:16,750 --> 00:14:19,610
Now let me show you a more complex
example, okay?

325
00:14:19,610 --> 00:14:21,820
This is a more complex example, okay?

326
00:14:21,820 --> 00:14:24,750
It has four variables and the numbers are
a little bit bigger.

327
00:14:24,750 --> 00:14:27,050
We want to make your life little bit more
miserable.

328
00:14:27,050 --> 00:14:27,570
Okay?

329
00:14:27,570 --> 00:14:29,240
That's what we do in this class.

330
00:14:29,240 --> 00:14:31,020
And so what you see is you see the table
now.

331
00:14:31,020 --> 00:14:32,050
It has four entries.

332
00:14:32,050 --> 00:14:33,950
It has a bunch of capacity as well.

333
00:14:33,950 --> 00:14:35,900
Okay?
And now what you can do, okay?

334
00:14:35,900 --> 00:14:40,600
You just stop this video and then you
start filling this beautiful table on

335
00:14:40,600 --> 00:14:42,070
your screen.
Actually don't do that, right?

336
00:14:42,070 --> 00:14:42,940
So, don't do that.

337
00:14:42,940 --> 00:14:45,660
Okay, just you know, just print the
lecture.

338
00:14:45,660 --> 00:14:47,700
Okay?
So, I'm going to do the work for you.

339
00:14:47,700 --> 00:14:48,000
Okay?

340
00:14:48,000 --> 00:14:53,460
This is the complete You know, the, the
complete

341
00:14:53,460 --> 00:14:56,950
values for all these tables and they are
entirely correct.

342
00:14:56,950 --> 00:14:57,470
Okay?

343
00:14:57,470 --> 00:14:59,080
You can trust us on that.

344
00:14:59,080 --> 00:15:01,590
And then you see this bottom right corner,
right?

345
00:15:01,590 --> 00:15:02,590
That's my precious.

346
00:15:02,590 --> 00:15:06,020
That's what the val, the optimum value of
the knapsack and then

347
00:15:06,020 --> 00:15:09,640
that's what I can use to trace back the
value of the optimal solution.

348
00:15:09,640 --> 00:15:10,400
Look at this guy.

349
00:15:10,400 --> 00:15:11,880
Okay?
It has value of 44.

350
00:15:11,880 --> 00:15:13,450
Is it equal to 42?
No?

351
00:15:13,450 --> 00:15:16,380
So you know that you selected item four.
Okay?

352
00:15:16,380 --> 00:15:19,480
So you decrease the capacity by the weight
of that particular item.

353
00:15:19,480 --> 00:15:20,690
You get to this position.

354
00:15:20,690 --> 00:15:23,610
You see, oh, is it the same.
yes, it's the same.

355
00:15:23,610 --> 00:15:25,570
yes, it's the same.
Oh, it's not the same.

356
00:15:25,570 --> 00:15:27,530
So you know that you selected item one.

357
00:15:27,530 --> 00:15:31,300
So the optimal solution here is selecting
item one and item four.

358
00:15:31,300 --> 00:15:32,180
Okay?

359
00:15:32,180 --> 00:15:35,260
So, and, the value of your decision
variables are exactly that, right?

360
00:15:35,260 --> 00:15:37,760
So you see that x1 is equal one, the next
two

361
00:15:37,760 --> 00:15:40,700
are equal to zero, and x4 is equal to one,
okay?

362
00:15:40,700 --> 00:15:45,670
So this dynamic programming algorithm here
is basically computing All the value okay?

363
00:15:45,670 --> 00:15:50,020
Of your decision variables and satisfying
the capacity constraint .Okay?

364
00:15:50,020 --> 00:15:54,490
Now an, an interesting question for you is
how long does this algorithm take?

365
00:15:54,490 --> 00:15:56,360
Well, it's pretty easy, right?
So the only thing

366
00:15:56,360 --> 00:15:58,580
that we are really doing is filling this
table.

367
00:15:58,580 --> 00:15:59,130
Okay?

368
00:15:59,130 --> 00:16:01,710
And to fill any one of the entries in this
table, the only

369
00:16:01,710 --> 00:16:05,590
thing that you do is looking at two values
On the prior column, okay?

370
00:16:05,590 --> 00:16:08,560
So it's basically an algorithm which takes
the time

371
00:16:08,560 --> 00:16:12,250
that it takes is you know, as
scientifically, k times,

372
00:16:12,250 --> 00:16:15,270
the k times n, where k, capital K is size

373
00:16:15,270 --> 00:16:18,550
of knapsack and n is the number of items,
okay.

374
00:16:18,550 --> 00:16:21,600
Now you're going to see wow, this is
really interesting,

375
00:16:21,600 --> 00:16:26,120
we just saw p equals lp, this algorithm is
polynomial, right?

376
00:16:26,120 --> 00:16:27,110
Right?

377
00:16:27,110 --> 00:16:30,370
So are we going to get a Nobel prize?
No, not really, right.

378
00:16:30,370 --> 00:16:31,150
So why?

379
00:16:31,150 --> 00:16:35,110
Because on a computer this capital K
there, okay, can be

380
00:16:35,110 --> 00:16:41,360
uncoded using binary notation by log of K,
capital K bit.

381
00:16:41,360 --> 00:16:42,030
Okay?

382
00:16:42,030 --> 00:16:46,740
And because of that when you look at this
complexity it's actually exponential in

383
00:16:46,740 --> 00:16:48,000
the size.

384
00:16:48,000 --> 00:16:53,755
Of, of the input because I can co, encode
this in, input with log k bits.

385
00:16:53,755 --> 00:16:53,980
Okay?

386
00:16:53,980 --> 00:16:56,790
So this is of use the exponential in that
number.

387
00:16:56,790 --> 00:16:57,410
Okay?

388
00:16:57,410 --> 00:16:59,310
So, so what do we have here?

389
00:16:59,310 --> 00:17:01,930
Well, we have an algorithm which is called
pseudo-polynomial.

390
00:17:01,930 --> 00:17:05,260
That basically means that if these numbers
are small this algorithm is polynomial.

391
00:17:05,260 --> 00:17:08,518
It works very well when the numbers are
small, okay?

392
00:17:08,518 --> 00:17:12,330
So every time you know you've, you've
essentially an knapsack whose capacity

393
00:17:12,330 --> 00:17:15,720
is reasonably small this is a very very
efficient algorithm.

394
00:17:15,720 --> 00:17:19,540
If the capacity starts getting huge and
huge and huge and you have a

395
00:17:19,540 --> 00:17:23,660
lot of items, you know, you're are going
to get into some, some issues.

396
00:17:23,660 --> 00:17:26,540
And can you guess what the issues are?
Okay?

397
00:17:26,540 --> 00:17:29,500
Remember, what we are computing was, is
this table okay?

398
00:17:29,500 --> 00:17:31,100
This capital K is huge.

399
00:17:31,100 --> 00:17:34,010
This table is going to get bigger and
bigger and bigger and bigger,

400
00:17:34,010 --> 00:17:37,550
okay, and that's one of the problems that
you have with dynamic programming.

401
00:17:37,550 --> 00:17:40,290
Okay guys, so this is the first hat, okay?

402
00:17:40,290 --> 00:17:43,600
Now I wanted to present to you, this is
dynamic programming, okay?

403
00:17:43,600 --> 00:17:45,380
So you saw we can compute oh, you know,

404
00:17:45,380 --> 00:17:48,000
of human solutions to doing abstract
problem with dynamic programming.

405
00:17:48,000 --> 00:17:51,530
In the next lecture, we'll see another
technique which is essentially solving.

406
00:17:51,530 --> 00:17:54,570
This, this, you know, recursive equation
using a top down approach.

407
00:17:54,570 --> 00:17:54,850
Okay?

408
00:17:54,850 --> 00:17:56,420
See you next time, guys, thank you.