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 let's 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 additional assumption that their integral.
In addition to these two n numbers,
we are given one more which is called the capacity, capital W,
again we'll assume this is non-negative and an integer.
The role of these integrality assumptions will become clear in due time.
The knapsack problem,
the responsibility of an algorithm is to select a subset of the items.
What do we want?
We want as much value as possible, so
we want to 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 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 subroutine 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 subproblems.
And we're going to arrive at the sub problems for
the knapsack problem just as we did for max weight independent sets by doing
a thought experiment about the optimal solution, and
understanding what it has to look like in terms of solutions to smaller subproblems.
The bottom line of this thought experiment,
the deliverable will be a recurrence.
It will be a formula which tells us how the optimal value of
one subproblem depends on the value of smaller subproblems.
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 right most 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 literally ordered one,
two, three, all the way up to n, and
then the analog of the right most 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 the 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, s star,
amongst the first n minus 1 items with a weight even bigger than that of s,
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 subproblem.
So if we're going to delete the last item, then we can't talk about s,
because 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 independent set problem,
we removed the right most vertex from the optimal solution before talking about its
optimality in a smaller subproblem.
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?
All right, so the correct answer is C.
So back in the independent set problem what we said is if we remove the right
most vertex, then what's left is optimal for the residual independent
set problem we get by plucking off the right most two vertices.
Here when we remove the nth item from the optimal solution S,
the claim is what we get is optimal for the knapsack problem involving the first
n-1 items and a residual knapsack capacity of W-w sub n.
So 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 could rule out quickly.
It just doesn't type check.
So capital W, that's the knapsack capacity, so that's in units of size.
Little v sub n, that's the item's value.
So that's in dollars, so
it doesn't really make sense to talk the difference between those two.
They're just apples and oranges.
Part D, if you were worried about feasibility at any point.
So, if you take capital S and you remove the nth item, what have you done?
You have taken a set of items whose 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 at most capital W minus little w sub n.
So, S minus n wouldn't be feasible for
this reduced to this residual knapsack capacity W- 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-1 items,
than S minus item n, if you had a full knapsack capacity of 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.
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.
All right, so why is capital C correct?
Well, this is going to have the same spirit of case two of our weighted
independent set thought experiment.
So let me give you the proof.
The proof is going to be the usual contradiction analogous to case 2 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- wn.
Call that supposedly better solution S*, so what can we do to get a contradiction?
Well, let's just take S* which involves only the first n-1 items.
Let's add item n to it since S* has total size and most W-w sub n and
item n has size W sub n, the result has total size of W so
it's a feasible solution to take S* and extend it by item number n.
And if S* had more value than S with n removed,
then S* 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 with n removed had value 1000.
If S* was better, it had a value 1,050.
Well then we just put n back in and it has value 1150 which contradicts the purported
optimal value of S* which had total value merely 1100.
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 the solution S*.
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
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 optimum 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.