Problem Overview

Loading...

來自 University of California San Diego 的課程

Algorithmic Toolbox

4373 個評分

University of California San Diego

Algorithmic Toolbox

4373 個評分

課程 1（共 6 門，Specialization 数据结构与算法）

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

從本節課中

Dynamic Programming 2

In this module, we continue practicing implementing dynamic programming solutions.

Problem Overview5:52

Knapsack with Repetitions10:19

Knapsack without Repetitions18:49

Final Remarks7:40

與講師見面

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering
Pavel Pevzner
Professor
Department of Computer Science and Engineering
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics

Hi, today we are going to revisit the Knapsack problem,

the problem that we already discussed in the Greedy Algorithms module.

In this very first segment of this lesson,

we will recall the definition of this problem, as well as motivate its study

by providing a few examples of applying this problem in real life.

Our first example is the following.

Assume that you are given a time slot, say two or three minutes, and

together with this time slot, you are given a set of TV commercials.

For each commercial, you know its revenue and you know its duration,

that is length in minutes, and your goal is to maximize the revenue.

That is, you would like to select some subset of your available TV commercials,

so that the total revenue is as large as possible while

the total length does not exceed the length of your available time slot.

In our second example, you are given a fixed budget and your goal is to purchase

a number of computers so that to maximize the total performance.

Again, we assume that the part of your input in this case is a set of available

computers or machine and for each machine you know its price and its performance.

Both the considerated problems can be easily seen to be

special cases of the following general problem known as the Knapsack Problem.

In this problem,

you are given a set of items together with the total capacity of the knapsack.

For each item you know its value and its weight.

For example, the value of the green item here is four, while its weight is 12.

And your goal is to select the subset of items such that the total value is as

large as possible while the total weight is at most, the capacity of the knapsack.

In our case, the total capacity of the knapsack is equal to 15.

There are two versions of the knapsack problem.

Fractional knapsack and discrete knapsack.So, for

the fractional version, which you are already familiar with, you can take any

fraction off of any item, while in the discrete version, for each item,

you either take the whole item in your knapsack or you do not take it at all.

So, in turn, the discrete version has two variants also.

So, the first variant is knapsack with repetitions.

So in this case, you are given an unlimited quantity of each item.

While in the knapsack without repetitions,

you are given just a single copy of each item.

So we know already that the fractional knapsack problem can be solved

by a simple greedy algorithm.

Such an algorithm at each iteration just picks an element,

an item with the currently maximal value per unit of weight.

This strategy, however, doesn't work for

the discrete version of the knapsack problem.

So instead of using greedy strategy,

we will design a dynamic programming solution to find an optimal value.

Now let me give you a toy example.

Assume that our input consists of a knapsack of total capacity of ten and

four items shown on the slide.

Then the optimal value for the knapsack without repetitions problem

is equal to 46 and it can be obtained by taking the first item and

the third item into your knapsack.

At the same time for the knapsack with repetitions problem.

The optimal value in this case is equal to 48 and it can be obtained

by taking one copy of the first item and two copies of the last item.

Finally, for the fractional knapsack problem, the optimal value is equal

to 48 and a half and can be obtained by taking the first item,

the second item, and half of the last item.

Let's also use this example to show that greedy algorithm fails for

the discrete version of the knapsack problem.

Recall that the greedy strategy for

this problem is to first compute the value per unit of weight for each item.

In our case, the value per unit of weight for the first item is equal to five,

for the second item it is equal to four and two thirds, for the third

item it is equal to four, and for the last item it is equal to four and one half.

So the first item has maximal value per unit of weight so

we take it into our solution.

The next available item with the maximal

value per unit of weight is the second one, so we take it also into the solution.

Now the remaining capacity is too small to add any other element.

So this is our constructed solution, and it has weight,

it has value 44 which is not optimal, we know it already.

For example here, by replacing the second item by the third item,

we will increase the total value.

This actually means that taking an element

with a maximal value per unit of weight is not a safe step.

Just by doing this we can lose a possibility to construct

an optimal solution.

Right, so this means actually that

we need some other algorithm to solve this problem optimally.

And we will design such an algorithm based on the dynamic programming technique in

the next video.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取