0:20

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.

Â 1:01

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.

Â 3:19

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.

Â 3:45

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.

Â 4:13

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.

Â