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]

Â