0:54

So we call them greedy algorithms or heuristic.

And you will see why later on.

I will tell you why we call them this. Okay?

So, once again, think about the temple is collapsing.

We saw that in the previous lecture. You know the various item that you have.

You know the value that each of them has.

You also know the weight of them, and

obviously you know the capacity of your knapsack.

Okay?

So, which item do we start taking?

Okay?

That's the basic idea, that's what we're trying to do.

And, let's, let's, this is the first thing that you can say, okay?

So, I'm going to take very small things because I believe that I can pack

many of them, and then I'm going to give you a good value at the end.

Okay this is the first idea.

You look at the item, you sort them

essentially by weight and you start packing them, okay?

So what you see there, you see the

small weights at the beginning, higher weights until the

very heavy mask over there.

And so you start picking these, these, these various item.

Essentially until you exceed the capacity of your knapsack.

At this point essentially, you can't pack any more item, so you're

fixed with what you've selected so far, and you get a particular value.

In this particular case, 10 million.

That's one greedy algorithm and the greediness

here was selecting the smaller item first

and you put them in until there is no space on the knapsack, okay?

Very simple greedy algorithm.

We saw another one, okay, during the previous lecture.

And that was selecting the most valuable item first, okay?

So, to re-, to, to remind you of what we did.

We sorted the item by value, okay?

Starting with the mask, and so on and so forth, okay?

And then you pick the highest value item.

And then immediately, there are items that you cannot put

inside the knapsack at this point, because they are too big.

And then we take

some of these warriors, okay.

In this particular case one of them, to actually get the value of

the knapsack, in this particular case, which is about, which is 14 millions here.

Better solution in this particular case, the greediness what, what's different

here is not the smallest item, it was the most valuable item.

That's the second idea of a greedy algorithm.

Okay, in this particularly this one was better, you know, I

can easily design a case where the first one would be better.

Now can we do better than these two.

Okay, I'm going to show you an interesting idea here because

we're going to start focusing on the structure of the problem.

Okay, and you've seen in this class, structure

is going to come back all the time.

Okay, exploring the structure of the problem.

So, when you look at this thing, one of the things you

can do is that, okay, so most valuable item is interesting, but this

may be very, very, very heavy, and the smaller one may have,

you know, they may be tiny, tiny, tiny but they have no value.

Okay?

What you want to do is really find something which is called value density.

Okay, how much value do you have per kilo

that you will have to lift and, and transport, okay.

So look at all these items.

We know the value, you know the weight, you can

divide these two things and you get a sense on

how, you know, what is the value of one kilo

of this warrior, of one kilo of this mask, okay.

And now you see that you can sort them by that, by, by that order and

this becomes the most valuable and then you see the ordering has

changed completely and now you start

packing them inside this new ordering, okay.

So you, you, you put this, this particular artifact first.

And as soon as you do that, you can't select the mask anymore.

And then you put the tablet and you get eight kilo.

So you still have some room to actually put a particular warrior there.

And you get a value which is 18 millions, okay?

So here we're exploiting the structure.

We really look at the, the, the value per weight, per

weight unit and we got a better solution in this particular case.

Okay?

Now you may ask, is this the best we can do?

Is this optimal?

Is there any way I can improve?

And obviously, this class is going to be

all about, you know, improving on the greedy algorithm.

And in this particular case, there is a very simple solution which does better.

You select these two tablets and you get a value

which is 20 million, okay.

We still don't know if it's optimal, right, you know,

but in this particular case we can actually prove this.

So, in a sense, the main messages today is to show you

that in practice there are many different greedy algorithms that you can build.

You have to think, you know, creatively.

What is the best greedy algorithms that I could get?

And some will be better than others in different kinds of instances, okay, so,

and, and so you may actually use several of them at the same time.

The advantage of this is that they are very easy

to use, very easy to design, okay, they can be very,

very fast, they give you a first solution, they tell

you, okay, you know, now I understand something about this problems.

I know that this is at least a baseline,

and I have to start doing better than this.

They have a lot of issues obviously, okay?

So, there is no solution guarantees in general.

You don't know much you can improve them, you don't know how good they are.

5:29

the, the quality of these heuristics may value from

problems to problem, from instances to instances, and so on.

And one of the things that I have assumed

here is that you can build the solution easily.

Finding a feasible solution is not an issue.

And there are many problems in practice where

just finding a feasible solution is very very difficult.

So, you will have to, to do something

else than a greedy algorithm in that particular case.

Or you will have to change the notion of what

a solution is.

So, but these are some issues that we'll have to deal with once again and these

issues, the, the most advanced techniques that we

will present in this class, we'll address those.

So, one of the things that you should do in this class is, when you start

on a problem, okay, what we highly recommend

is that you start with a greedy algorithm.

Try to understand what the problem is.

Get a base line, that's what you have to improve and than

afterwards you going to use some of the techniques that we will present,

you know, constraint programming, mixed

integer programming, local search, to actually

improve on the greedy and find out how much you can improve.

And once again, some of these techniques are also going to give you a way to assess

the value of the greedy algorithm, or any solution that you can come up with, okay?

So this is essentially the main message.

I'll see you next time, okay?

And what we going to do in the rest of the, of, of, of the, the knapsack lecture

is show you how you can find, reliably, the reliability feasible solution.

How you can build high quality solution which

are robust across a wide range of impact.

And also give you a way to actually find out

if these solutions are optimal or not, how good there are.

Okay?

This is essentially, the, the most advanced techniques are allowing

you to do these things that a greedy algorithm cannot, okay?

See you next time, thank you guys.

[BLANK_AUDIO]