Dynamic Programming and the 0/1 knapsack

问题:

I'm having some trouble understanding dynamic programming, even though I've read through so many resources trying to understand.

I understand an example given of dynamic programming using the fibonacci algorithm. I understand how if you use the divide and conquer approach to it, you'll end up solving some sub-problems multiple times, and dynamic programming takes care of that by solving those overlapping subproblems but only once (and storing them for future reference). However, I have been introduced to dynamic programming in my class using the 0/1 knapsack problem as an example, and I don't really understand the example, or how it illustrates dynamic programming, or how it's in anyway similar to the fibonacci example.

Here are the slides related to it:

I mainly understand what is going on until the last slide, where it says f(i,y) = max{....}

What exactly am I finding the max of? Why am I finding the max of anything at all? And most importantly, what does this have to do with dynamic programming? I don't understand the relation, like I do when it comes to the fibonacci example. I honestly have no clue what this knapsack problem has anything to do with dynamic programming because it doesn't even seem comparable in anyway to using the fibonacci example to illustrate dynamic programming. Like I don't see any parallels or anything at all, and it really doesn't make much sense to me

回答1:

What exactly am I finding the max of?

f is the sum of the profits brought by all the items that you put in the knapsack. At stage i, there are two possibilities :

• you put item i in the knapsack, and you solve the problem for all remaining items, subtracting the weight of item i from your maximum weight,
• you don't put item i in the knapsack, and you solve the problem for all remaining items. This is a subproblem that you have already solved, since you are working backwards, so the link with dynamic programming should become apparent there.

The solution is the option that brings the highest profit, hence the max.

回答2:

Dynamic programming is just defining the problem in terms of simpler subproblems.

In the case of Fibonacci, we define the problem in terms of the two smaller terms.

In this case, we define the problem with some number of items and some capacity in terms of problems containing less items and possibly a smaller capacity.

---

f(i,y) is the maximum profit containing items i through n with a capacity of y.

Now we can define this as either including or excluding item i, and then getting the maximum profit for items i+1 through n.

When we exclude item i, this doesn't change the weight, so we can just look at the maximum profit for the same capacity, i.e. f(i+1, y), and the profit also doesn't change.

When we include item i, this changes the weight, specifically by the weight of item i, which is w_i, so we have to look up f(i+1, y - w_i). But then we also get the profit from item i, so we need to add its profit, i.e. p_i.

Now, since we want the maximum profit, we have to find the maximum of these two values, giving us:

f(i, y) = max{f(i+1, j), f(i+1, y - w_i) + p_i}

If you're still having trouble understanding it, I suggest you construct yourself an example to work through - no amount of explaining quite measures up to seeing it actually working, and using this to get some intuition for why we do things the way we do.