Knapsack 1 - intuition

Loading...

来自 The University of Melbourne 的课程

Discrete Optimization

205 个评分

The University of Melbourne

Discrete Optimization

205 个评分

Tired of solving Sudokus by hand? This class teaches you how to solve complex search problems with discrete optimization concepts and algorithms, including constraint programming, local search, and mixed-integer programming. Optimization technology is ubiquitous in our society. It schedules planes and their crews, coordinates the production of steel, and organizes the transportation of iron ore from the mines to the ports. Optimization clears the day-ahead and real-time markets to deliver electricity to millions of people. It organizes kidney exchanges and cancer treatments and helps scientists understand the fundamental fabric of life, control complex chemical reactions, and design drugs that may benefit billions of individuals. This class is an introduction to discrete optimization and exposes students to some of the most fundamental concepts and algorithms in the field. It covers constraint programming, local search, and mixed-integer programming from their foundations to their applications for complex practical problems in areas such as scheduling, vehicle routing, supply-chain optimization, and resource allocation.

从本节课中

Knapsack

These lectures introduce optimization problems and some optimization techniques through the knapsack problem, one of the most well-known problem in the field. It discusses how to formalize and model optimization problems using knapsack as an example. It then reviews how to apply dynamic programming and branch and bound to the knapsack problem, providing intuition behind these two fundamental optimization techniques. The concept of relaxation and search are also discussed.

Knapsack 1 - intuition2:33

Knapsack 2 - greedy algorithms7:13

Knapsack 3 - modeling8:56

Knapsack 4 - dynamic programming17:57

Knapsack 5 - relaxation, branch and bound14:53

Knapsack 6 - search strategies, depth first, best first, least discrepancy14:45

与讲师见面

Professor Pascal Van Hentenryck
Dr. Carleton Coffrin
Adjunct Lecturer
Computing and Information Systems

Okay guys Discrete Optimization. We going to start very, very slowly.

So what you're going to see here is amazingly simply.

We are building the intuitions.

And in the next couple of lectures, we are basically solving these knapsack problems.

Going from very simple things to more interesting things, okay?

So, we want to introduce greedy algorithm.

And what would Indiana Jones do if he

doesn't know anything about discrete optimization and hasn't

taken the class in Coursera, right? So, this is what you have.

The temple is collapsing and you have all these beautiful artifacts, right?

So you have the Agamemnon mask. You have the Terracotta warriors.

You have the Sumerian tablets.

And of course, you know, Indiana Jones is pretty smart, right?

So he can evaluate the value of every one of these item immediately right?

So, 13 millions for the mask, 1 million for

the, the little statues over there, right? So the warrior.

Okay so now what Indiana Jones is going to say, he's going to say oh, but I also

have to evaluate the size of my knapsack

and he can figure it out very quickly right?

So this is about ten kilos, okay?

And then obviously what he has to do and once again he's really clever, right?

He has to evaluate the, the weight of every one of these artifacts as well.

Okay? And once you have all these things, okay?

What Indiana Jones is going to do is to say okay I'm going to

pick up the right ones, what I believe are the right ones.

Not knowing anything about optimization.

And of course you can't resist, right?

The first thing you're going to do is take this mask, it's so beautiful, right?

So that's the first thing he does okay?

And obviously that's eight kilos.

So there is only two kilos left inside the knapsack, okay?

So essentially, these items cannot be selected anymore.

The only thing

which is left are the warriors there.

And Indiana Jones is going to select one of them

and then exhaust the capacity of its, of its knapsack.

Okay, the value here is about 14, is exactly 14 millions.

And the whole point of this class is going to say.

Can we do better than this?

One of the things we'll do here, is talk in

the first, in the next lecture is talk about greedy algorithm.

And what you just saw is essentially, a very

simple instance of a greedy algorithm.

We take the most valuable item first and then

the next valuable item that can fit into a knapsack.

But there are many, many possible greedy algorithms.

In the next lecture, we'll review some of them.

And then afterwards, what we'll do

is basically look at more sophisticated technique.

I told you, very simple lecture, this is the first one.

See you next time.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2018 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取