# Is the knapsack problem NP-hard when $v_i=i$?

The knapsack problem is NP-hard and can be formulated as: \begin{align}&\text{maximize } \sum_{i=1}^n v_i x_i,\tag{P1}\\& \text{subject to } \sum_{i=1}^n w_i x_i \leq W,\\&\text{and } x_i \in \{0,1\}.\end{align}

What if $$v_i=i$$? Is it still NP-hard?

\begin{align}&\text{maximize } \sum_{i=1}^n ix_i,\tag{P2}\\& \text{subject to } \sum_{i=1}^n w_i x_i \leq W,\\&\text{and } x_i \in \{0,1\}.\end{align}

I am trying to reduce (P1) to (P2). Given an instance of (P1), I create the same number of items, same weights. Now, I have to relate the solutions to (P1) and (P2).

• You cannot use the same weights... One problem is that values might be quite large. Suppose you have a value of $2^n$ (takes $n$ bits to encode). Then you will need $2^n$ variables, which presumably would take at least $2^n$ bits to encode (unless you allow sparse encodings – you don't specify this). Another problem is that weights could repeat. Apr 12 '20 at 21:51

No, this problem is in $$\mathbf{P}$$. The main point being that the sum of all the values is $$1 + 2 \ldots + n = \frac{n(n+1)}{2} = \mathcal{O}(n^2)$$, which is polynomial in the input size. Without the extra restriction of $$v_i = i$$, the sum of all the values could be exponential in the input size, as the values are represented in binary in the input.

So we can define $$DP[i][v]$$, where $$1 \leq i \leq n$$ and $$0 \leq v \leq \frac{n(n+1)}{2}$$, to be the minimum weight needed to get a value of at least $$v$$, using only the first $$i$$ items. If it cannot be achieved, we'll set $$DP[i][v] = INF$$. The final answer is the maximum $$v$$ such that $$DP[n][v] \leq W$$.

The DP values can be calculated as follows:

$$DP[i][v] = \min(DP[i-1][v], w_i + DP[i-1][v - v_i])$$.

The first term considers the possibility of the $$i^{th}$$ item not being chosen, and the second term is the possibility that it is chosen.

So the entire problem can be solved in $$\mathcal{O}(n^3)$$ time and $$\mathcal{O}(n^3)$$ space, which can be reduced to $$\mathcal{O}(n^2)$$ space by just reusing two arrays of size $$\frac{n(n+1)}{2} + 1$$.

• What makes this polytime and solving the normal 0-1 knapsack problem using the same approach not polytime? I mean if I define the same table $DP[i][v]$ for (P1) in the question, what would the complexity be? Is it $O(nV)$, where $V$ is the sum of values?
– zdm
Apr 14 '20 at 21:31
• @zdm Yes, the exact same algorithm would work for the normal problem as well, but in time $\mathcal{O}(nV)$, as you point out. That would be a pseudo-polynomial time algorithm in the general problem, but is polynomial time in this setting because we have the extra bound on its values. The other more common pseudo-poly time algo for knapsack is $\mathcal{O}(nW)$, as can be seen here. Apr 15 '20 at 1:24