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.