5
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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)

In case you're interested, I've done a C++ implementation here, and a comparison between the different ways to retrieve the optimal solution here

Improve this answer
$\endgroup$
3
  • $\begingroup$ Think it should be $O(n + W)$. $\endgroup$
    – Max
    Mar 31, 2022 at 8:20
  • $\begingroup$ 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. $\endgroup$
    – fontanf
    Mar 31, 2022 at 8:33
  • 2
    $\begingroup$ 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. $\endgroup$
    – Paul Bouman
    Mar 31, 2022 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.