Explore
For Enterprise
Join for Free
Log In

艺术与人文
商务
计算机科学
数据科学
信息技术
健康
数学和逻辑
个人发展
物理科学与工程
社会科学
语言学习
學位
證書

瀏覽 Coursera 的全部課程

瀏覽
搜索
企業版
登錄
免費加入

Problem Overview

Loading...

Algorithmic Toolbox

加州大学圣地亚哥分校

4.7（4,928 個評分） | 160K 名學生已註冊

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

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). Do you have technical problems? Write to us: coursera@hse.ru

查看授課大綱

您將學習的技能

Dynamic Programming, Debugging, Software Testing, Algorithms, Computer Programming

審閱

4.7（4,928 個評分）

5 stars
3,672 ratings
4 stars
1,001 ratings
3 stars
175 ratings
2 stars
35 ratings
1 star
45 ratings

PR

Feb 10, 2019

The course is perfectly designed. The perfect start for those who start with data structures and algorithms. The Dynamic programming was a little bit tough but overall course is perfectly designed

RS

Dec 23, 2018

This course is just awesome and outstanding in every term. Teachers are very good at explaining even the toughest of problems and really helped throughout the course, i enjoyed and leaned a lot.

從本節課中

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
Michael Levin
Lecturer
Neil Rhodes
Adjunct Faculty
Pavel Pevzner
Professor
Daniel M Kane
Assistant Professor

腳本

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 獲取

Coursera
關於
管理團隊
工作機會
目錄
證書
MasterTrack™ 證書
學位
企業版
政府版

社區
Learners
Partners
Developers
Beta Testers
Translators

連接
博客
Facebook
領英
Twitter
Instagram
YouTube
技術博客

更多
條款
隱私
幫助
內容訪問
媒體
聯繫我們
目錄
附屬公司