0:00

In this video we will be designing a dynamic formatting solution for

Â the Knapsack without Repetitions problem.

Â Recall that in this problem we're give a single copy of each item.

Â So this is also to remind you the formal statement of the problem, so we emphasize

Â once again that we are not allowed to take more than a single copy of each item.

Â Well, we already know that our previous same reason cannot produce the right

Â answer for our new very namely for the Knapsack without repetitions problems.

Â Well this is simply because in our toy example is that optimal value for

Â the Knapsack with repetitions was 48 while the optimal value for

Â the Knapsack without repetitions was 46.

Â So this means that if we just run our previous algorithm,

Â it will produce an incorrect result.

Â Still it is important to understand where our algorithms,

Â where our reasoning more generally fails for this problem.

Â 1:21

That is the last item.

Â So we argue, well similarly to the previous case that if we take this item

Â out of the current knapsack, then what we get must be an optimal solution for

Â a knapsack of smaller weight, namely of total weight W- wn.

Â So if we take we the smaller solution and we add the nth item to it,

Â we get an optimal solution for the initial knapsack of total weight, W.

Â I assume however, that the optimal solution for

Â the smaller knapsack, already contains the nth item.

Â This means that we cannot add another copy of the nth element to it,

Â right, because then the resulting solution will contain two copies

Â of the nth element which is now forbidden by the problem formulation.

Â So this is why we need to come up with a different notion of a subproblem.

Â So still, let's take a closer look at our optimal solution.

Â It is not difficult to see that there are only two cases,

Â either it contains the lost item, or it doesn't contain it.

Â I assume that it contains, and

Â let's again take this nth item out of our current solution.

Â So what is left?

Â First of all, it is some solution for a knapsack of total weight,

Â capital W- wn, and it also uses only items from 1 to n- 1,

Â because, well, we just took out the nth item, right?

Â 3:01

If, on the other hand, the initial optimal solution for

Â the knapsack of total weight W does not contain the nth item,

Â well, then it contains only items from 1 to n minus 1.

Â Right?

Â Well this simple observation will help us to get the right

Â definition of a subproblem for this version of the knapsack problem.

Â 3:23

Well on the previous slide we argued as follows.

Â Consider an optimal solution for a knapsack of total weight capital W.

Â And there are two cases.

Â Either it can contain the last item or it doesn't contain.

Â If it contains we can take it out, and reduce the problem for

Â small knapsack using only items from one to n minus one.

Â On the other hand, if it doesn't contain the nth item, then we'll reduce

Â it to another case when the knapsack only uses items from 1 to n-1.

Â In any case, we reduce the number of items and in the first case,

Â we also reduce the size of the knapsack, the total weight of the knapsack.

Â We might continue this process, and express the solution for

Â all sub-problems through solutions to force up subproblems.

Â If we continue in the same fashion what we get somewhere in the middle is

Â a solution for a knapsack of some weight that uses some first i items.

Â Well let's just use this as a definition of our subproblem.

Â Namely, for any w, from 0 to W, and

Â for any i, from 0 to n, let's denote by value of w and

Â i the maximum value that can be achieved by using only items from 1 to i,

Â and whose total weight is at most w.

Â Right, then it is easy to express it through solutions for

Â smaller such problems.

Â Once again, value of w and i, is a subset, is an optimal

Â 5:12

value of a subset, of the first items who stole the weight is utmost w.

Â So we know that in this optimal subset,

Â either there is the i-th item or the i-th item is not contained in it.

Â So there are two cases.

Â So we need to select the maximum out of two cases.

Â And the first case if we take the i-th item out what is left

Â is an optimal solution for the following problem.

Â We are allowed only to use the first i-1 items and the total weight should

Â be no more than w-wi, so this is the first term under the maximum.

Â 5:51

In the second case, if the i-th item is not used in an optimal solution,

Â then we just know that the optimal solution is the same as for

Â the knapsack of total weight, W, using only the first i- 1 items.

Â 6:21

We now done our recurrent formula into a dynamic problem in algorithm.

Â As usual, we start from initialization namely with your set all the values of 0,

Â j to 0 for all j and all the values of w, 0 to 0.

Â Well, this just expresses the fact that if we have no items, well,

Â then the value is zero.

Â If we have the knapsack of total weight zero,

Â then the total value's also zero, of course.

Â Then recall, now, we need to somehow compute, all other values of w, i.

Â 7:07

W, smaller w and i- 1 and W and i- 1.

Â This means that we always reduce the problem from

Â Wi to something with smaller number of items, to i- 1.

Â This actually helps us to understand that

Â it makes sense to gradually increase the number of allowable items.

Â And this is why we have in this pseudocode an outer loop where i goes from 1 to n.

Â When i is fixed, we will compute all the values of W, i.

Â So for this, we also go from W equal to 1 to capital W and do the following.

Â So now, i and W are fixed, we need to compute value of W, i.

Â First, we just check what is the value of, what is the solution for

Â the subproblem when we use the knapsack of the same weight w but

Â we only use the first i-1 items.

Â 8:11

This is implemented as follows.

Â We first just assign value of w, i to value of w, i-1.

Â Then we need to check whether we can improve this value by using the i-th item.

Â First of all we can only do this if the weight of the ice item does not exceed

Â the weight of the current knapsack which is just W.

Â So, if it doesn't exceed we see what happens if we take an optimal value for

Â the knapsack of the total weight w minus wi.

Â That is filled only by elements from 1 to i minus 1,

Â and add the i-th element to it.

Â If it gives a larger value than we currently have, we will update the value

Â of wi, so in the end we just return the value of capital w and n.

Â Because this is the solution to our initial problem.

Â So this a solution for a knapsack of size capital

Â w that uses just all the n items, right?

Â Now so it is clear that this algorithm is correct just because

Â it directly implements the recurrent formula that we already discussed.

Â So let's analyze its running time.

Â It is not difficult to show, again, that its running time is actually the same.

Â It is again n multiplied by W.

Â Well, this is again just because we have two loops here.

Â So this is the first loop with n iterations, and

Â this is the inner loop with W iterations.

Â And what is going on inside only takes some constant time.

Â 10:03

Now let's apply the algorithm that we've just designed to our toy example.

Â Recall that we need to store the values of all subproblems for Wi,

Â for all W from zero to ten, and all i from zero to four, in our case.

Â For these purposes, it is natural to use a two-dimensional table, or

Â two-dimensional array.

Â You can see such a two-dimensional array on the slide already filled in.

Â So here we have i, so all the rows of our

Â columns are by all possible way of i, and

Â all the columns in this set by all possible values of W.

Â Right, we start by initializing the first row, and

Â the first column of this table by zero.

Â That is, we fill this row by zeroes and

Â we fill this column by zeroes also.

Â Then we start filling in this table row by row.

Â That is, we first fill in this cell, then this cell,

Â then this cell, then this cell, and so on.

Â So we go like this.

Â So we first fill in this row, then fill in this row,

Â then fill in this row and then fill in this row.

Â So the results in value 46 is actually

Â the answer to our initial problem.

Â Now, let me show you how some particular value, just through this trait,

Â let me show you how some particular value in this table was computed.

Â For example, consider this cell.

Â 11:53

So formally, this is value,

Â value(10, 2).

Â Which means that this is an optimal value of a knapsack of total

Â weight 10 that only uses the first two items.

Â So assume that we don't know what to put here.

Â 12:18

So we just need to compute it right now.

Â So let's argue as we did before.

Â So this is a knapsack of total weight 10 that uses only the first two items.

Â Well, we then say that the second item is either used or not.

Â So if it is not used, then this is the same as filling in

Â the Knapsack of total weight ten just using the first item.

Â And we already know this value because it is in the previous row.

Â So this is value 10, 1, right?

Â So the value in this case is 30.

Â On the other hand, if the second item is used,

Â then if we take it out, what is left is an optimal solution for

Â a knapsack of total weight 10 minus 3.

Â Because 3 is the weight of the second item,

Â which means that it is an optimal solution for a knapsack of size 7.

Â Of total weight 7 that only uses the first,

Â that is only allowed to use the first item.

Â Also, if we add this item to,

Â if we add the second item to the solution, we get 30 plus 14.

Â Which is much better than without using the second item, right?

Â So that's why we have 44 here.

Â 14:17

Reconstructing an optimal solution in this particular problem I mean finding

Â not only the optimal value for the knapsack of size of total weight.

Â But the subset of items that lead to this optimal value itself.

Â For this we first create a boolean array of size four.

Â In this array, we will mark, for each item,

Â whether it is used in an optimal solution or not.

Â Now what we're going to do is to back trace the path that led us

Â to the optimal value, 46.

Â In particular, let's try to understand how this value of 46 was computed.

Â 15:02

Well, first of all, 46 is formally value of 10, 4,

Â that is is an optimal value for

Â a knapsack of total weight ten using the first four items.

Â We argued that the fourth item is either used or not.

Â If it is not used, then this value is the same as the value 10,

Â 3, which is shown here.

Â That is the value of the knapsack of the same weight, using the first three items.

Â If on the other hand it is used, then what is left must be an optimal solution for

Â a knapsack of size 10 minus 2 which is 8, that uses also the first three items.

Â Well this value is already computed, it is 30, so

Â we need to compute the maximum among 30 plus 9,

Â because, well the value of the last item is 9 and 46.

Â In this particular case there, the maximum is equal to 46 which

Â means that we decided at this point not to use the last item, right?

Â So we put 0 into our boolean array to indicate this, and we move to this cell.

Â 16:18

Again, let's try to understand how this value was computed.

Â It was computed as the maximum value of two

Â numbers which depend on the following values.

Â So either we do not use the third item, then it is the same,

Â has the value of this cell or we use the third item.

Â In this case, what remains is an knapsack of size, of total weight 6,

Â and using the first two items and its value is 30.

Â 16:49

Plus the weight of the third item, which is 16.

Â In this particular case, 30 plus 16 is larger than 44,

Â which means that this value of 46 was computed using this value.

Â This, in turn, means that we decided to use the third item.

Â Let's mark it by putting 1 into our boolean array.

Â Now we stay in this cell and we try to understand how it was computed.

Â It was computed as a maximum over this 30 and

Â this 0, plus fourteen.

Â Right, in this case, the first value is larger so

Â we move to this cell and we mark that we decided not to use the second item.

Â Okay and finally, we realize that we arrived at this value

Â 30 from the right, from the left upper corner.

Â Right?

Â So, this way we reconstructed the wall optimal solution.

Â Once again, we backtraced the path that led us to the optimal value.

Â 18:11

Here, what is shown here, is that we decided to use the first item and

Â the third item.

Â So let's check that it indeed gives us the optimal value of 46.

Â So indeed if we compute the sum of the weight of the first and

Â the third item, it is 10.

Â And while the total value is 30 plus 16 which is 46 indeed.

Â And as I said before this technique is usually used in dynamic

Â programming algorithms to reconstruct the optimal solution.

Â