Intuition behind Knapsack 0-1 dynamic programming solution?

1
votes

I've been studying dynamic programming as part of a course and have struggle for a few days with the DP solution for the knapsack 0-1 problem. My understanding of the problem and solution is this:

we have items (A, B, C, D), a knapsack that holds weight W = 10 maximum, and the weights/values of each item is A = 2w/1v, 2w/3v, 5w/8v, 6w,5v.

The solution requires that we look at subproblems where we restrict the knapsack weight from 0 -> W and the items from A -> D.

What I don't understand is

  1. How does one arrive at this solution intuitively?
  2. Why does the solution work even if the items are ordered differently since we need to iterate through each of the items?
  3. How does the DP subproblem solution account for all possible combinations of knapsack solutions if one did this without DP and use a brute-force try all combinations approach?
1
algorithmdynamic-programming
Please visit this link. It contains detailed explanation of Knapsack Problem including the intuition behind it. Here is the link: medium.com/@fabianterh/… - AKSingh
@AKSingh the article doesn't really explain how to arrive at the solution of deriving the subproblem unfortunately - alex
It does explain why you use the table and what does table represent and other things. What is missing? - AKSingh

1 Answers

0
votes

  1. Not sure what you mean by "intuitively" but we can develop an understanding of how to form recurrence relations and apply them to problem parameters.

  2. The soution works regardless of order since each subproblem relates to the current item and the subproblems we already visited. The recurrence does account for "all combinations"; which is why if we visit A -> B, when we get to C, we are essentially trying A B AB C AC BC and ABC; if we rather visit A -> C, then B; we'd get the same overall set of possibilities, given that addition is associative (A C AC B BA BC BAC). (We don't actually visit all combinations, see 3.)

  3. We account for all possibilities by generally visiting the entire search space of W*N. Since we are bound by W, all weight sum combinations will fall at or below it, and what the DP does is record the best seen value for each of those achievable weights. When we reach the ith item, we don't need to know the specific combinations of items creating all the sums (we may want to track back for the actual items but that does not require an exhaustive record). For each weight we iterate over (we iterate over all possible weights each time we visit an item), we just need to know (1) the best value seen at the same weight (so not using this item), and (2) the best value seen at a weight lower by this item's weight (if we're using this item then we want to add its value to the best value seen at that lower weight so the two weights together represent the current weight we are at in the weight iteration). We choose the best of (1) and (2) for the value at dp[i][w].