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