What is the link between table in knapsack problem and dynamic programming?

1
votes

Apologies for a very newbie question as I am unable to find answer to it from various resources.

In knapsack algorithm, we construct a table, e.g. in https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

I have read about the knapsack problem in Kleinberg's book. As per my understanding, dynamic programming is about breaking the problem into overlapping sub-problems - however, I have seen this table used to solve the knapsack in various books/online resources. I can't seem to wrap my head around how is this table linked to dynamic programming? Are we memoizing anything in this table? It seems to me to be a clever solution to the knapsack, but not a dynamic programming one. I have seen videos and texts where they solve the problem either by using a table or using a dynamic programming solution, but no one seems to provide a link between the two.

1
algorithmdynamic-programmingknapsack-problem
Watch Parenthesization, Edit Distance, Knapsack by Erik Demaine for the MIT OpenCourseWare. He teaches how to solve Knapsack using Dynamic Programming in pseudo-polynomial time - starting at 43:15. Great lesson! – jweyrich
Thanks but still haven't got my answer. There is no table in the video. Regarding the solution in the video, I had come to a similar solution but what happens when the input is like this: {(5kg, $4), (2kg, $2), (5kg ,$4), (2kg, $3)} [kg is for weight and $ is for value]. In a recursive solution, in each step, we will have to explore each subproblem's tree (we can memoize it), otherwise if we go sequentially, then the result will be $4 instead of the optimal solution which is $5. – Mustehssun Iqbal
knapsack capacity is 5kg in above example. – Mustehssun Iqbal

1 Answers

1
votes

It's still dynamic programming. The only distinction is that the dynamic programming algorithm is still not polynomial in n, but in both n and W. For these types of problems, you have to distinguish between values that arise natural due to the input, and values that are part of the input.

Your input consists of n different items and the number W; W is explicit, not implied by the size of the input. Because we are using some efficient encoding (i.e., binary) to provide W, the size of W is exponential in the encoding of W. That is, the input contains O(lg W) bits representing W, but the table we build has W rows (or columns, deepening on how you view it). That make the algorithm exponential in the input size.

However, if we relax our usual rule that the input has to be represented efficiently, we could specify W using "unary" notation; W 1s in the input instead of a binary representation. Now you can claim that, because the input size is polynomial in n and W, rather than in n and lg W as before, that the DP table is also polynomial in the input.

This is roughly the difference between strong and weak NP-hardness: if a problem is weakly NP-hard, then a polynomial-time algorithm (usually based on dynamic programming) can be found if we specify a unary encoding of some numerical parameter rather than the usual binary encoding.