Is Knapsack restricted to integers between 1 and 100 still NP-complete?

Question

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.

Answer 1

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$.