# Dynamic program for knapsack in $O(W)$ space?

A familiar dynamic programming algorithm for the binary knapsack problem \begin{align} \text{maximize}\quad & v \cdot x \\ \text{subject to} \quad & w \cdot x \leq W \\ \quad&x_i \text{ binary} \end{align}

is as follows: Let $$m[i, w]$$ denote the highest utility achievable in a knapsack that uses only the first $$i$$ items and has capacity $$w$$. Then the optimal objective value is $$m[n, W]$$ which can be computed using the following recursion relation:

\begin{align} m[0, w] &= 0 \\ m[i, w] &= \begin{cases} m[i-1, w], \quad &w_i > W \\ \min\lbrace m[i-1, w], m[i-1, w - w_i] + v_i\rbrace, \quad& w_i \leq W \end{cases} \end{align} A standard way to implement this algorithm is to fill an $$n \times W$$ array with the $$m[i, w]$$-values, then determine the optimal solution by iterating backwards from $$m[n, W]$$ by observing that $$x_i = 1$$ if and only if $$m[i, w] > m[i-1, w]$$.

As Wikipedia notes (emphasis mine),

This solution will therefore run in $$O(nW)$$ time and $$O(nW)$$ space. (If we only need the value $$m[n,W]$$, we can modify the code so that the amount of memory required is $$O(W)$$ which stores the recent two lines of the array m.)

Wikipedia doesn't cite any sources here, and I am curious if this is truly the state of the art. Suppose that I do want the $$x$$-vector and not just the objective value. Is $$O(nW)$$-space the best we can do?

• ... or is there a clever way to organize the two-line table that keeps track of whether or not each $$x_i = 1$$ and uses $$O(W)$$-space after all?
• ... or is there a way to prove that the solution cannot use less than $$O(nW)$$-space unless (for example) P = NP?

N.B. This question is exclusively concerned with the implementation of the item-weight-based dynamic program given above. I know that there are other algorithms for the knapsack problem with lighter space requirements.

There is a recursive scheme which makes it possible to retrieve the optimal solution with an $$O(n + W)$$ memory. It is described in Section 3.3 of the book "Knapsack Problems" (Kellerer et al., 2004)
• Think it should be $O(n + W)$.
• I updated the answer, but I'm not sure that it really requires $O(n)$ space. The number of items in the solution is smaller than $W$. $O(n)$ space is required to store the instance, $O(\log n)$ is required to store the recursive call stack, but I don't see where $O(n)$ space is required inside the algorithm itself. Commented Mar 31, 2022 at 8:33
• I think it at least depends on whether you require the output vector to be encoded as a full vector, which gives you $O(n)$ for the construction of the output, or whether you allow it to be encoded as a sparse vector. In the latter case it seems to make sense to assume $W \geq m \geq n$ with $m$ the number of items in the output, as $W=m$ kind of implies all items use capacity $1$. If you allow items that do not consume $0$ capacity the story would be a bit different, but you could easily get rid of those edge cases by appropiate preprocessing/postprocessing. Commented Mar 31, 2022 at 10:55