Knapsack without Repetitions

Loading...

Do curso por Saint Petersburg State University

Competitive Programmer's Core Skills

22 classificações

Saint Petersburg State University

Competitive Programmer's Core Skills

22 classificações

During the course, you’ll learn everything needed to participate in real competitions — that’s the main goal. Along the way you’ll also gain useful skills for which competitive programmers are so highly valued by employers: ability to write efficient, reliable, and compact code, manage your time well when it’s limited, apply basic algorithmic ideas to real problems, etc. We start from the very beginning by teaching you what competitions there are, what are their rules, what specifics problems have, how to read problem statements, how to organize your work, and what you should and shouldn’t do. So it’s fine if you’ve never taken part in programming competitions before. We’ll focus on skills essential to competitive programming: inventing solutions and proving their correctness, estimating their running time, testing and debugging programs, how to benefit from structuring code. We’ll also cover basic algorithmic ideas: brute force search, dynamic programming, greedy algorithms, segment trees. On competitions, there are a lot of specific pitfalls, perilous to beginners — but that’s not to worry, as we’ll go through the most common of them: integer overflow and issues with fractional numbers, troubles of particular programming languages, how to get unstuck in general. And, you’ll hone all these skills by solving practice problems, which are just like problems on real competitions. You could use any of the following programming languages: C, C++, C#, Haskell, Java, JavaScript, Python 2, Python 3, Ruby, Rust, Scala. We assume that you already know how to write simplest programs in one of these.

Na lição

Dynamic Programming 2

We continue applying dynamic programming technique to various problems.

Knapsack with Repetitions14:06

Knapsack without Repetitions11:49

Final Remarks5:36

Conheça os instrutores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Alexander Logunov
Competitive Programming Co-coach at SPbSU
Kirill Simonov
Competitive Programming Co-Coach
Aliaksei Tolstsikau
Senior lecturer
Faculty of applied mathematics and computer science, Belarusian State University Academic programs coordinator, Yandex, Judge of Belarusian olympiad in Informatics. Judge of Western subregional contest of Northern Eurasia. ICPC World finalist (2010), Topcoder collegiate challenge finalist (2007), Google code jam finalist (2008).

[MUSIC]

In this video, we turn to the version of the knapsack problem, where repetitions

are not allowed, namely for the knapsack without repetitions problem.

Recall that in this problem, once again, each item,

there is just a single copy of each item.

So we are not allowed to take more than one copy of any item.

Before designing an algorithm, let's just try to understand whether we can use

the subproblems used in the previous version.

So assume that we can see there are some optimal solution for

a knapsack of capacity W, and assume that we somehow

know that it uses the last item of weight, wn- 1.

And we try to extract this item out of the solution and

to solve the remaining problem of capacity, W- wn- 1.

So in this case, it is not excluded that the optimal solution for

the results in subproblem of capacity, W- wn- 1, actually contains the last item.

And since it contains it,

we cannot add this item to this solution together the solution for

our original subproblem because it will create two copies of the last item, right?

However, we consider it the last, namely, n- 1 item here on purpose because

this will eventually lead us to defining the right notion of the subproblem.

Namely, assume that the n- first item is used in an optimal solution.

Then if we take this out from the bag of capacity capital W,

then what we get must be an optimal solution for

the bag of total capacity W- wn- 1 that

uses only items from 0 to n- 2, right?

Because we are not allowed to use the last item anymore.

On the other hand, if the last item is not used in the optimal solution for

the bag of capacity W, then what we know is that it must

use only the items with indices from 0 to n- 2.

This actually means that in both these cases, we either reduce the total

capacity or we reduce the set of available items, right?

And finally, this leads us to the following subproblem.

So for two parameters u and i, where u ranges from 0 to capital W and

i ranges from 0 to n, let's define value (u,

i) to be the optimal value of the bag of capacity

u that uses only the first i items, okay?

So this allows us to write the following recurrence relation.

So we actually start with the base case.

When i = 0, this actually means that we do not have any items.

So value (u, 0) = 0 for any u.

And also, when u = 0, this actually means that we have the bag of total capacity 0.

So value (0, i) = 0 for any i.

And the recurrence relation that we get here is actually even simpler than in

the previous case.

So we either use the item i- 1 in our solution or not.

So what we need to compute in order to find the value (u,

i) is actually the maximum of the following two values.

The value (u- wi- 1, i- 1) + vi- 1,

or just value (u, i- 1).

So in the first case,

actually, we are going to use the i- first item in our solution.

And in the second case, we are not going to use this item.

And also, among these two terms, the first one is used only in case

the weight of the i- first item does not exceed u, okay?

So this recurrence relation, as usual,

can be easily transformed into a recursive algorithm that you see now on the slide.

As usual, we use a table T which is, in this case, just a dictionary.

And we only start computing the value (u, i) if it is not yet in the table.

And we do this just following our recurrence relation.

So namely, in the eighth line,

we actually compute the second term in our recurrence relation.

So we initialize T (u, i) to be equal to just actually the value (ui- 1).

And then, in the case when the value of the i- 1 item does not exceed u,

we check whether the current value can be improved

by actually taking an optimal solution for u- wi- 1 and

adding this i- first item of this solution, okay?

So this gives us a recursive algorithm.

And as usual, it can be transformed into an iterative algorithm.

In this case, instead of using dictionary for

storing all the intermediate solutions, we actually use a two dimensional table.

So we use a two dimensional table because each our

subproblem is actually specified by two parameters, by u and i.

So for this reason, we need a table which is indexed, so

rows are indexed by u, for example, and columns are indexed by y, okay?

Then we just fill in this table by gradually

increasing the parameters u and i.

This gives us an algorithm whose running time is equal to big O(nW).

The reason is simple.

So in this case, we just have two nested loops, two for nested loops.

Or put it otherwise, we have nW subproblems, and for

each subproblem, it takes us a constant amount of work to compute its value.

The space requirement is the same, it is big O(nW),

just in particular, because we need to store a table of that size, right?

At the same time, it is not so difficult to improve

actually the space used by this algorithm by noting that

we do not need to store the whole table all the time.

Namely, when computing the values in the current column,

it is enough to know all the values from the previous column.

So instead of storing the whole table,

we can actually keep storing the current row and the previous row, okay?

Then let's also discuss how to reconstruct the solution, namely,

what we've already computed is the optimal value.

Now, what we are going to do is to explain how to find

the optimal subset of items, right?

As usually, this can be done just by reconstructing the solution

somehow from right to left or just to unwind the solution from right to left.

So we start just from the last cell of our table,

from the cell where u = W and i = n.

And then we follow the following simple rule.

So each time if value (u, i) = value (u,

i- 1), then this basically means that our

optimal solution does not use the item i- 1.

So in this case, we just update i to i- 1 and proceed.

In the opposite case, when value (u,

i) = value (u- wi- 1, i- 1) + vi,

we actually know that the i's item is used, okay?

So we store this information somehow and

we update u to u- wi- 1 and i to i- 1, okay?

So this eventually leads us somehow from the bottom right

corner of our table to the top left column in our table, okay?

Now, as a final remark,

let me also explain how it is possible to arrive to this

dynamic programming solution by optimizing the corresponding brute force solution.

So what is a brute force solution in this case?

Since we have only a single copy of each item, we can do the following.

We process items one by one, starting from item number 0 and

ending with item number n- 1.

And for each item, we decide whether we take it in our solution or not.

So what you see here is a recursive implementation of this idea.

As you see, we have two parameters here, items and last.

So items, just as in our previous brute force solution,

denotes that set of currently used items.

And the last is actually the index of the last item which we consider it, okay?

So in the seventh line in this code, we actually

just decide not to use the item with index last.

So actually, we just increase last by 1 and make a recursive call, okay?

In the eigth line, if the item with index last + 1

actually can be added to our current solution, namely,

if adding this item does not exceed the weight, capital W,

then we try to add it to our current set of items.

We increase last by 1, we make the recursive call.

And if it gives a better solution, then we actually store this result.

So then by running this algorithm,

you will find a solution for small datasets, but for

large datasets, it will not work, of course, because it is too slow.

It actually goes through all possible subsets of size 2 to the n.

However, it can be optimized as usual.

So it can be optimized just by noticing that the only thing we need to

know about the current subset of items is actually

the index of the last item that we made some solution about, and

also the total weight of the current set of items.

So just by replacing the collection of items just by their total weight,

we actually get back our previous solution based

on the dynamic programming technique.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play