The title pretty much says it all. I want to know if Knapsack is still NP-complete when the weights, values, and weight limit are restricted to a finite set of values. I figure that it wouldn't be because clearly for very small finite sets it isn't. (E.g., if you must use integers from 1 to 3.) That said, I'm struggling to find a polynomial-time algorithm.

One thought I had was since there are a finite set of possible inputs and outputs, could your algorithm just be a massive chain of if statements? I'm not sure whether this even would count as an "algorithm" though.

  • $\begingroup$ I would say we could consider an algorithm a procedure that looks up in a table the corresponding output according to the input. It would be constant time, but this approach is not feasible and unrealistic. You would also need somehow to precompute all those values. $\endgroup$ – JhonRM Feb 22 '20 at 1:28
  • $\begingroup$ A problem is called "strongly NP-hard if it remains NP-hard even when all numeric input values are represented in unary. Knapsack is not strongly NP-hard. $\endgroup$ – Antti Röyskö Feb 23 '20 at 2:18

Let $V(i, W)$ be the maximum sum of the values of the items among the first $i$ items so that the sum of the weights is less than or equal to $W$, then we have

$$V(i, W)=\max\{V(i-1, W), v_i+V(i-1,W-w_i)\}$$

where $v_i$ and $w_i$ are respectively the value and the weight of the $i$th item. Suppose there are $n$ items and the capacity limit is $W_\max$, then the problem is equivalently to compute $V(n, W_\max)$. We can use the recursion formula above to compute the following values in order: $$V(1,1),\ldots,V(1,W_\max),V(2,1),\ldots,V(2,W_\max),\ldots,V(n,1),\ldots,V(n,W_\max).$$

This is the classical dynamic programming method to solve the Knapsack problem. Since it takes $O(1)$ time to compute each $V(\cdot,\cdot)$ and there are $O(nW_\max)$ such values to compute, the overall running time is $O(nW_\max)$. Since you restrict $W_\max\le 100$, the overall running time becomes $O(100n)=O(n)$, which is indeed polynomial in $n$.

  • $\begingroup$ OK, but what about 200? :-P $\endgroup$ – j_random_hacker Feb 22 '20 at 13:53
  • $\begingroup$ @j_random_hacker, if you look at xskxzr's answer, the dynamic programming algorithm is $O(n W)$, if $W$ is limited, it is certainly polynomial in $n$. The overall size of the input data is polynomial in $n$, so there is no blowup. It is polynomial for each limit. $\endgroup$ – vonbrand Feb 23 '20 at 19:12
  • $\begingroup$ @vonbrand: I know, it was intended to be a joke. $\endgroup$ – j_random_hacker Feb 25 '20 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.