# Knapsack

The Knapsack problem is defined as follows. Given a set of $$n$$ items $$i=1,\ldots, n$$, each with weight $$w_i$$ and value $$v_i$$, and a knapsack capacity $$C$$, find a subset of items such that the total weight is bounded by $$C$$ and the total value is maximized.

The decision version of Knapsack is that, given a goal value, decide whether there exists a subset satisfying the capacity constraint and with the total value no less than the goal value. This decision version of Knapsack is NP-complete.

### Dynamic Programming

Knapsack can be solved using dynamic programming. Let $$V(i, w)$$ be the maximum value achieved by choosing a subset from the first $$i$$ items such that the total weight is exactly $$w$$. We have $$i$$ ranges from 0 to $$n$$, and $$w$$ ranges from 0 to $$C$$.

Let $$V(0, w) = 0$$ for all $$w$$, and define the recurrence
$V(i+1, w) = \max \begin{cases} V(i, w) \\ V(i, w-w_{i+1}) + v_{i+1} \end{cases}$
The $$V(i, w)$$ table has about $$nC$$ entries, and can be computed in time $$O(nC)$$. The optimum is obtained at the entry with maximum value. The optimal set can be obtained by tracking the table. This is a pseudo-polynomial algorithm.

The following is a different way of defining the recurrence. Let $$W(i, v)$$ be the minimum weight achieved by a subset from the first $$i$$ items such that the total value is exactly $late v$. Define $$W(i, v) =\infty$$ if no subset exists. Let $$V$$ be the maximum value of the items, and then $$v$$ ranges from 0 to $$nV$$.

Let $$W(0, v) =\infty$$, and define the recurrence
$W(i+1, v) = \min \begin{cases} W(i, v) \\ W(i, v-v_{i+1}) + w_{i+1} \end{cases}$

Computing the $$W(i, v)$$ table takes time $$O(n^2 V)$$. The optimum is the maximum $$v$$ such that $$W(n, v) \leq C$$.

### Efficient Approximation: FPTAS

The dynamic programming algorithm above can be adapted to get an approximate algorithm running in polynomial time. The idea is to scale down the values to be bounded by a polynomial of $$n$$.

We wish to get a solution of at least $$(1-\epsilon) v^\star$$ where $$v^\star$$ is the optimal value. Let $$K= \epsilon V/n$$, and define the new value for each item to be
$v_i’ = \lfloor \frac{v_i}{K} \rfloor.$
This is the same as truncating the last $$\lceil \log K\rceil$$ bits of the values.

Then we run the dynamic programming to compute $$W(i, v)$$, and find the optimal set; the output is the total value of this set.

Next we argue that the output $$v’ \geq (1-\epsilon) v^\star$$. Suppose the optimal set achieving $$v^\star$$ is $$S$$, and the (approximate) optimal set achieving $$v’$$ is $$S’$$.

• $$v^\star = \sum_{i\in S} v_i \geq \sum_{i\in S’} v_i = v’$$, since $$S$$ is optimal for the original problem
• $$\sum_{i\in S’} v_i \geq \sum_{i\in S’} v_i’$$, since $$v_i\geq v_i’$$
• $$\sum_{i\in S’} v_i’ \geq \sum_{i\in S} v_i’$$, since $$S’$$ is optimal for the truncated version
• $$\sum_{i\in S} v_i’ \geq \sum_{i\in S} (v_i-K) \geq v^\star – nK$$
• $$v^\star – nK = v^\star – \epsilon V \geq (1 – \epsilon) v^\star$$, assuming $$w_i\leq C$$ and $$v^\star\geq V$$.

Therefore, we get $$v^\star \geq v’ \geq (1-\epsilon)v^\star$$. The running time of the algorithm is $$O(n^2 V/K) = O(n^3 /\epsilon)$$, and thus polynomial in $$n$$ and $$1/\epsilon$$.

A polynomial-time approximation scheme (PTAS) for an optimization problem is an algorithm such that, for any $$\epsilon \geq 0$$ and any instance of size $$n$$, it outputs a solution with a relative error at most $$\epsilon$$ and runs in time polynomial in $$n$$. A fully polynomial-time approximation scheme (FPTAS) is a PTAS such that the running time is polynomial in both $$n$$ and $$\epsilon$$.

A solution $$v$$ with a relative error at most $$\epsilon$$ is within $$(1\pm \epsilon) v^\star$$ for the optimal solution $$v^\star$$. Usually, it is also that $$v^\star\leq v\leq (1+\epsilon)v^\star$$ for a minimization problem, and $$v^\star \geq v\geq (1-\epsilon)v^\star$$.