1
00:00:00,440 --> 00:00:03,370
Okay, guys, discrete optimization,
knapsack algorithm.

2
00:00:03,370 --> 00:00:07,370
We're going to look at greedy algorithm
again, okay, and this time in more detail.

3
00:00:07,370 --> 00:00:10,830
The key point here is that what we want to
do

4
00:00:10,830 --> 00:00:15,000
is that something that can give you
solutions very quickly, okay?

5
00:00:15,000 --> 00:00:16,820
And that's going to give you a baseline

6
00:00:16,820 --> 00:00:18,820
on everything that you will do afterwards,
okay?

7
00:00:18,820 --> 00:00:22,810
So you can start with this, and then can
look at how to improve it later on, okay?

8
00:00:22,810 --> 00:00:25,920
So, even greedy algorithm is an
interesting topic, okay?

9
00:00:25,920 --> 00:00:30,170
Designing them may be very complex on some
problems and they may vary in qualities.

10
00:00:30,170 --> 00:00:32,600
So, what I'm going to do today is
basically

11
00:00:32,600 --> 00:00:35,900
illustrate various kinds of greedy
approach on the knapsack

12
00:00:35,900 --> 00:00:39,620
problem and, you know, in a sense give you
the intuition of how you can design them.

13
00:00:39,620 --> 00:00:41,380
And you can be creative on these guys, as
well.

14
00:00:41,380 --> 00:00:42,100
Okay?

15
00:00:42,100 --> 00:00:45,240
So, the key idea on all the greedy
algorithms is going to be the same.

16
00:00:45,240 --> 00:00:47,580
You're going to pick one item at a time in
a greedy fashion.

17
00:00:47,580 --> 00:00:51,360
And the only thing that's going to differ
is the meaning of greedy

18
00:00:51,360 --> 00:00:53,070
in every one of these algorithms.
Okay?

19
00:00:54,470 --> 00:00:56,580
So we call them greedy algorithms or
heuristic.

20
00:00:56,580 --> 00:00:57,620
And you will see why later on.

21
00:00:57,620 --> 00:00:59,930
I will tell you why we call them this.
Okay?

22
00:00:59,930 --> 00:01:02,970
So, once again, think about the temple is
collapsing.

23
00:01:02,970 --> 00:01:07,180
We saw that in the previous lecture.
You know the various item that you have.

24
00:01:07,180 --> 00:01:09,480
You know the value that each of them has.

25
00:01:09,480 --> 00:01:11,140
You also know the weight of them, and

26
00:01:11,140 --> 00:01:13,510
obviously you know the capacity of your
knapsack.

27
00:01:13,510 --> 00:01:14,220
Okay?

28
00:01:14,220 --> 00:01:16,170
So, which item do we start taking?

29
00:01:16,170 --> 00:01:16,430
Okay?

30
00:01:16,430 --> 00:01:19,260
That's the basic idea, that's what we're
trying to do.

31
00:01:19,260 --> 00:01:22,830
And, let's, let's, this is the first thing
that you can say, okay?

32
00:01:22,830 --> 00:01:25,770
So, I'm going to take very small things
because I believe that I can pack

33
00:01:25,770 --> 00:01:29,730
many of them, and then I'm going to give
you a good value at the end.

34
00:01:29,730 --> 00:01:31,200
Okay this is the first idea.

35
00:01:31,200 --> 00:01:33,200
You look at the item, you sort them

36
00:01:33,200 --> 00:01:37,290
essentially by weight and you start
packing them, okay?

37
00:01:37,290 --> 00:01:38,700
So what you see there, you see the

38
00:01:38,700 --> 00:01:41,230
small weights at the beginning, higher
weights until the

39
00:01:41,230 --> 00:01:43,270
very heavy mask over there.

40
00:01:43,270 --> 00:01:46,550
And so you start picking these, these,
these various item.

41
00:01:46,550 --> 00:01:50,290
Essentially until you exceed the capacity
of your knapsack.

42
00:01:50,290 --> 00:01:53,860
At this point essentially, you can't pack
any more item, so you're

43
00:01:53,860 --> 00:01:57,140
fixed with what you've selected so far,
and you get a particular value.

44
00:01:57,140 --> 00:01:58,880
In this particular case, 10 million.

45
00:01:58,880 --> 00:02:01,210
That's one greedy algorithm and the
greediness

46
00:02:01,210 --> 00:02:03,580
here was selecting the smaller item first

47
00:02:03,580 --> 00:02:07,050
and you put them in until there is no
space on the knapsack, okay?

48
00:02:07,050 --> 00:02:09,040
Very simple greedy algorithm.

49
00:02:09,040 --> 00:02:12,240
We saw another one, okay, during the
previous lecture.

50
00:02:12,240 --> 00:02:16,330
And that was selecting the most valuable
item first, okay?

51
00:02:16,330 --> 00:02:18,670
So, to re-, to, to remind you of what we
did.

52
00:02:18,670 --> 00:02:21,130
We sorted the item by value, okay?

53
00:02:21,130 --> 00:02:24,200
Starting with the mask, and so on and so
forth, okay?

54
00:02:24,200 --> 00:02:25,990
And then you pick the highest value item.

55
00:02:25,990 --> 00:02:28,270
And then immediately, there are items that
you cannot put

56
00:02:28,270 --> 00:02:31,380
inside the knapsack at this point, because
they are too big.

57
00:02:31,380 --> 00:02:32,150
And then we take

58
00:02:32,150 --> 00:02:34,580
some of these warriors, okay.

59
00:02:34,580 --> 00:02:38,920
In this particular case one of them, to
actually get the value of

60
00:02:38,920 --> 00:02:42,310
the knapsack, in this particular case,
which is about, which is 14 millions here.

61
00:02:42,310 --> 00:02:45,960
Better solution in this particular case,
the greediness what, what's different

62
00:02:45,960 --> 00:02:49,490
here is not the smallest item, it was the
most valuable item.

63
00:02:49,490 --> 00:02:51,666
That's the second idea of a greedy
algorithm.

64
00:02:51,666 --> 00:02:54,660
Okay, in this particularly this one was
better, you know, I

65
00:02:54,660 --> 00:02:57,850
can easily design a case where the first
one would be better.

66
00:02:57,850 --> 00:02:59,720
Now can we do better than these two.

67
00:02:59,720 --> 00:03:02,940
Okay, I'm going to show you an interesting
idea here because

68
00:03:02,940 --> 00:03:05,560
we're going to start focusing on the
structure of the problem.

69
00:03:05,560 --> 00:03:07,610
Okay, and you've seen in this class,
structure

70
00:03:07,610 --> 00:03:09,280
is going to come back all the time.

71
00:03:09,280 --> 00:03:11,710
Okay, exploring the structure of the
problem.

72
00:03:11,710 --> 00:03:13,430
So, when you look at this thing, one of
the things you

73
00:03:13,430 --> 00:03:16,350
can do is that, okay, so most valuable
item is interesting, but this

74
00:03:16,350 --> 00:03:19,610
may be very, very, very heavy, and the
smaller one may have,

75
00:03:19,610 --> 00:03:22,100
you know, they may be tiny, tiny, tiny but
they have no value.

76
00:03:22,100 --> 00:03:22,660
Okay?

77
00:03:22,660 --> 00:03:26,550
What you want to do is really find
something which is called value density.

78
00:03:26,550 --> 00:03:28,870
Okay, how much value do you have per kilo

79
00:03:28,870 --> 00:03:32,560
that you will have to lift and, and
transport, okay.

80
00:03:32,560 --> 00:03:33,730
So look at all these items.

81
00:03:33,730 --> 00:03:35,320
We know the value, you know the weight,
you can

82
00:03:35,320 --> 00:03:38,180
divide these two things and you get a
sense on

83
00:03:38,180 --> 00:03:41,130
how, you know, what is the value of one
kilo

84
00:03:41,130 --> 00:03:45,160
of this warrior, of one kilo of this mask,
okay.

85
00:03:45,160 --> 00:03:48,810
And now you see that you can sort them by
that, by, by that order and

86
00:03:48,810 --> 00:03:51,750
this becomes the most valuable and then
you see the ordering has

87
00:03:51,750 --> 00:03:54,000
changed completely and now you start

88
00:03:54,000 --> 00:03:56,880
packing them inside this new ordering,
okay.

89
00:03:56,880 --> 00:04:00,810
So you, you, you put this, this particular
artifact first.

90
00:04:00,810 --> 00:04:04,010
And as soon as you do that, you can't
select the mask anymore.

91
00:04:04,010 --> 00:04:06,760
And then you put the tablet and you get
eight kilo.

92
00:04:06,760 --> 00:04:11,680
So you still have some room to actually
put a particular warrior there.

93
00:04:11,680 --> 00:04:14,280
And you get a value which is 18 millions,
okay?

94
00:04:14,280 --> 00:04:16,260
So here we're exploiting the structure.

95
00:04:16,260 --> 00:04:19,574
We really look at the, the, the value per
weight, per

96
00:04:19,574 --> 00:04:23,430
weight unit and we got a better solution
in this particular case.

97
00:04:23,430 --> 00:04:24,110
Okay?

98
00:04:24,110 --> 00:04:25,890
Now you may ask, is this the best we can
do?

99
00:04:25,890 --> 00:04:26,850
Is this optimal?

100
00:04:26,850 --> 00:04:28,610
Is there any way I can improve?

101
00:04:28,610 --> 00:04:30,310
And obviously, this class is going to be

102
00:04:30,310 --> 00:04:33,730
all about, you know, improving on the
greedy algorithm.

103
00:04:33,730 --> 00:04:36,860
And in this particular case, there is a
very simple solution which does better.

104
00:04:36,860 --> 00:04:39,530
You select these two tablets and you get a
value

105
00:04:39,530 --> 00:04:41,190
which is 20 million, okay.

106
00:04:41,190 --> 00:04:43,330
We still don't know if it's optimal,
right, you know,

107
00:04:43,330 --> 00:04:46,220
but in this particular case we can
actually prove this.

108
00:04:46,220 --> 00:04:49,720
So, in a sense, the main messages today is
to show you

109
00:04:49,720 --> 00:04:52,900
that in practice there are many different
greedy algorithms that you can build.

110
00:04:52,900 --> 00:04:54,840
You have to think, you know, creatively.

111
00:04:54,840 --> 00:04:57,330
What is the best greedy algorithms that I
could get?

112
00:04:57,330 --> 00:05:01,002
And some will be better than others in
different kinds of instances, okay, so,

113
00:05:01,002 --> 00:05:04,730
and, and so you may actually use several
of them at the same time.

114
00:05:04,730 --> 00:05:06,600
The advantage of this is that they are
very easy

115
00:05:06,600 --> 00:05:09,280
to use, very easy to design, okay, they
can be very,

116
00:05:09,280 --> 00:05:12,150
very fast, they give you a first solution,
they tell

117
00:05:12,150 --> 00:05:15,130
you, okay, you know, now I understand
something about this problems.

118
00:05:15,130 --> 00:05:18,070
I know that this is at least a baseline,

119
00:05:18,070 --> 00:05:20,550
and I have to start doing better than
this.

120
00:05:20,550 --> 00:05:22,830
They have a lot of issues obviously, okay?

121
00:05:22,830 --> 00:05:25,120
So, there is no solution guarantees in
general.

122
00:05:25,120 --> 00:05:28,130
You don't know much you can improve them,
you don't know how good they are.

123
00:05:29,840 --> 00:05:32,480
the, the quality of these heuristics may
value from

124
00:05:32,480 --> 00:05:36,038
problems to problem, from instances to
instances, and so on.

125
00:05:36,038 --> 00:05:37,820
And one of the things that I have assumed

126
00:05:37,820 --> 00:05:40,000
here is that you can build the solution
easily.

127
00:05:40,000 --> 00:05:43,530
Finding a feasible solution is not an
issue.

128
00:05:43,530 --> 00:05:45,150
And there are many problems in practice
where

129
00:05:45,150 --> 00:05:48,190
just finding a feasible solution is very
very difficult.

130
00:05:48,190 --> 00:05:51,340
So, you will have to, to do something

131
00:05:51,340 --> 00:05:53,195
else than a greedy algorithm in that
particular case.

132
00:05:53,195 --> 00:05:54,970
Or you will have to change the notion of
what

133
00:05:54,970 --> 00:05:56,180
a solution is.

134
00:05:56,180 --> 00:05:59,950
So, but these are some issues that we'll
have to deal with once again and these

135
00:05:59,950 --> 00:06:02,860
issues, the, the most advanced techniques
that we

136
00:06:02,860 --> 00:06:05,400
will present in this class, we'll address
those.

137
00:06:05,400 --> 00:06:08,760
So, one of the things that you should do
in this class is, when you start

138
00:06:08,760 --> 00:06:11,200
on a problem, okay, what we highly
recommend

139
00:06:11,200 --> 00:06:13,130
is that you start with a greedy algorithm.

140
00:06:13,130 --> 00:06:14,536
Try to understand what the problem is.

141
00:06:14,536 --> 00:06:17,032
Get a base line, that's what you have to
improve and than

142
00:06:17,032 --> 00:06:20,100
afterwards you going to use some of the
techniques that we will present,

143
00:06:20,100 --> 00:06:22,024
you know, constraint programming, mixed

144
00:06:22,024 --> 00:06:24,260
integer programming, local search, to
actually

145
00:06:24,260 --> 00:06:27,470
improve on the greedy and find out how
much you can improve.

146
00:06:27,470 --> 00:06:32,520
And once again, some of these techniques
are also going to give you a way to assess

147
00:06:32,520 --> 00:06:36,230
the value of the greedy algorithm, or any
solution that you can come up with, okay?

148
00:06:36,230 --> 00:06:38,300
So this is essentially the main message.

149
00:06:38,300 --> 00:06:40,410
I'll see you next time, okay?

150
00:06:40,410 --> 00:06:45,155
And what we going to do in the rest of
the, of, of, of the, the knapsack lecture

151
00:06:45,155 --> 00:06:50,310
is show you how you can find, reliably,
the reliability feasible solution.

152
00:06:50,310 --> 00:06:52,220
How you can build high quality solution
which

153
00:06:52,220 --> 00:06:54,670
are robust across a wide range of impact.

154
00:06:54,670 --> 00:06:57,530
And also give you a way to actually find
out

155
00:06:57,530 --> 00:07:00,350
if these solutions are optimal or not, how
good there are.

156
00:07:00,350 --> 00:07:00,605
Okay?

157
00:07:00,605 --> 00:07:03,965
This is essentially, the, the most
advanced techniques are allowing

158
00:07:03,965 --> 00:07:06,897
you to do these things that a greedy
algorithm cannot, okay?

159
00:07:06,897 --> 00:07:08,444
See you next time, thank you guys.

160
00:07:08,444 --> 00:07:13,860
[BLANK_AUDIO]