3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 12 at 21:51
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – zdm Apr 14 at 21:31
  • $\begingroup$ @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. $\endgroup$ – CodeChef Apr 15 at 1:24

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.