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

Question

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

Answer 1

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