So in these next two videos we'll give our second application of the dynamic
programming paradigm. It's to a quite well known problem, it's
called the knapsack problem. And we'll show how following the exact
same recipe that we used for computing independent sets in path graphs leads to
the very well known dynamic programming solution to this problem.
So lets jump right into the definition of a knapsack problem.
So the input is given by N items. So each item comes with a value V sub I,
the more the better for us, and also a size W sub I.
We're going to assume that both of these are non negative.
For the sizes we're going to make an additional assumption that they're
integral. In addition to these two N numbers we're
given one more which is called the capacity capital W, again we'll assume
this is both non negative and an integer. The role of this integrality assumptions
will become clear in due time. The knapsack problem, the responsibility
of an algorithm is, is to select a subset of the items.
What do we want? What we want is much value as possible.
So we want maximize the sum of the values of the items that we select.
So, what prevents us from picking everything, well, the sum of the sizes of
the items that we pick have to total to at most the capacity of capital W.
Now, I could tell you some cheesy story about a burglar breaking into a house
with a knapsack, with a certain size capital W, and wants to make away with
sort of the best loot possible. But, that would really be doing a
disservice to this problem, which is actually quite fundamental.
this problem comes up quite a bit, especially as a sub-routine in some
larger task. Really, just whenever you have sort of a
budget of a resource that you can use, and you want to use it in the smartest
way possible, that's basically the knapsack problem.
So, you can imagine how it would come up in a lot of contexts.
So let's now execute a recipe for developing a dynamic programming
algorithm. Remember the key to any dynamic
programming solution is to figure out what is the right set of sub-problems.
And we're going to arrive at the sub problems for the knapsack problem, just
as we did for max weight independence sets by doing a thought experiment about
the optimal solution, and understanding what it has to look
like, in terms of solutions to smaller sub problems.
The bottom line of this thought experiment, the deliverable, will be a
recurrence. It'll be a formula which tells us how the
optimal value of one subproblem depends on the value of smaller sub problems.
So to begin the thought experiment, fix an instance of knapsack, and let capital
S denote an optimal solution, a max value solution.
We began our previous thought experiment with a content-free statement that the
final vertex of a path is either in the optimal solution or it's not.
Now, what is the analog of the rightmost vertex in this knapsack problem?
Well, unlike a path graph, there's no intrinsic sequentiality to the items that
we're given. They're just an unordered set.
But it's actually useful to think of the items as sort of literally ordered,
one, two, three, all the way up to n. And then, the analog of the rightmost
vertex is just the final item. So the content free statement we're
going to work with here is either the last item belongs to the optimal
solution, capital S, or it doesn't. We'll again start with an easy case when
it doesn't. What we argued in the path graph problem
was that the max weight independent set in the analogous case one has to be
optimal if we just delete that rightmost edge from the graph.
So here the analogous claim is that this set s should still be optimal if we
delete the final item n from the knapsack instance.
The argument is the exact same near trivial contradiction.
If there was a different solution as star amongst the first and minus one items,
with weight even bigger than that of S. What we could regard this equally well as
a superior knapsack feasible solution, back with all N of the items,
but that contradicts the purported optimality of S.
So let's go through the slightly trickier case two together, using a quiz.
So suppose the optimal knapsack solution does, in fact, make use of this final
item, N. Now we want to talk about this being
somehow composed of an optimal solution to a smaller sub problem.
So if we're going to delete the last item, than we can't talk about S,
right?'Cause that's has the last item. So we need to remove the last item from S
before we talk about its optimality. That's analogous to back in the
independence set problem, we removed the right most vertex from the optimal
solution before talking about its optimality in a smaller sub problem.
So the question then is, if we take capital S, the optimal solution.
We remove item N. In what sense is the residual solution
optimal, put differently for what kind of knapsack instance, if any is that an
optimal solution for? Alright so the correct answer is C.
So back in the independent set problem what we said is if we remove the right
nosed vertex then what's left is optimal for the residual independent set problem
again by plucking off the right most two vertices.
Here when we remove the inth item from the optimal solution S, the claim is what
we get is optimal for the nap sack problem.
Involving the first n minus one items and a residual knapsack capacity of capital W
minus little w sub n. So the overall, the original knapsack
capacity with space reserved or deleted for the nth item.
So before I give you a quick proof, let me just briefly explain why a couple of
the other answers are not correct. so first of all, answer B, I hope you can
rule out quickly it just doesn't type check, so capital W that's the knapsack
capacity, so that's in units of size. Eh, little v sevin, that's the items
value, that's in dollars, so it doesn't really make sense to talk about the
difference between those two. They're just, it's apples and oranges.
part D, if you're worried about feasibility at any point, so if you take
capital S and remove the Nth item, what have you done, you've taken a set of
items who's, you know, size was at most capital W by feasibility of S and you've
removed an item with size Wn from it, so what remains has total size of most
capital W minus little w sub n. So, s and minus n would indeed be
feasible for this reduced this residual knapsack capacity capital W minus little
w sub n. A much more subtle point is part A.
That's a very natural one to guess. that turns out to not be correct.
So it turns out there might be smarter ways of using the first N minus one
items. Then S minus item N,
if you had a full knapsack of capacity of capital W to work with.
So that's a subtler point, and it's a good exercise for you to actually
convince yourself that A is wrong, and that there's no reason that when you
take out item N from S, and you still keep using the original knapsack
capacity, that this has to be optimal. That's not going to be true.
Alright, so why is capital C correct? Well this is going to have the same
spirit of case two, of our weighted independence set thought experiment.
So let me give you the proof. The proof is going to be the usual
contradiction analogous to case two of our argument in the weighted independent
set problem. So suppose there was something better
than S with N removed with the residual capacity W minus w sub n, call that
supposedly better solution S star. So what can we do to get a contradiction?
Well let's just take S star, which involves only the first n minus one
items. Let's add item n to it.
Since S star has total size of most capital W minus w should n and item N has
size W sub N. The results has total size at most
capital W. So the feasible solution to take S star
and extend it by item number N. And if S star had more value than S with
n removed, then S star with N included has more value than S.
So, for example, if S had total value, 1,100,
100 of which was coming from the nth item.
Then S would end removed, had value 1,000.
If S star was better, it had a value, 1,050.
Well, then we just put N back in. And it has value 1,150,
which contradicts the purported optimality of S star, which had total
value, merely 1,100. So, notice what's going on here.
So, in taking away W sub N for the knapsack capacity.
Before we look at, the residual problem. We're, in effect, reserving a buffer for
item N, if we ever need it, that's how we know
we're feasible when we stick N back into this solution as star.
That's analogous to deleting the penultimate vertex of the path, again as
a buffer to ensure feasibility when we include the Nth vertex back in the
independent set problem. So what was the point of this whole
thought experiment, which we've now completed?
Well, again, the point was to say, the optimal solution, whatever it is, it has
to have only one of two forms. We've narrowed the list of candidates
down to two possibilities. Either you just inherit the optimal
solution with one less item in the same knapsack capacity, or you look at the
optimal solution with one less item and less knapsack capacity by W sub N and you
extend that by item N. But those are the only two possibilities.
So, again, if we only knew which of these two cases were true,
if we only knew whether or not item N was in the optimal solution or not, in some
sense we could recursively compute the rest of the solution.
So just as that was enough to get us going with a dynamic programming
algorithm for weighted independent sets, so it goes with knapsack, as I'll show
you on the next video.