What's the time complexity bound for the Knapsack with real weights?

Question

Let's start with the formalism:
Let $W$ be the total weight of our bag, $1,...,n$ be our elements, $w_1,...,w_n$ their corresponding weights, and $v_1,...,v_n$ their corresponding values.

As is known, the knapsack problem for integer weights can be solved by dynamic programming (or equivalently, using recursion + memoization), with time complexity of $\mathcal O(nW)$, where $W$ is the total weight our bag can hold, and $n$ is the number of items.

However, for real numbered weights, the algorithm fails (just imagine a billion items with weight $<1$, and $W=1$). We probably can round them in a clever way and then scale them up to be integers again, but that'd blow the size of the problem up in an inacceptable way.

Another approach would be to use recursion instead of dynamic programming, because the idea behind the algorithm still works out - either the $n$'th item is in the optimal solution, or not.

However, even with memoization, we can easily choose our weights in a way so that all sums $$\sum_{ \begin{align} i&\in M\\ M&\subseteq \{1,..,n\} \end{align}} w_i$$

are distinct, leaving us with $2^n$ weight-sums to memoize.

Is there any optimal algorithm that manages to keep the time complexity pseudopolynomial?

Answer 1

If you have n random real numbers, then you have 2^n possible real sums. If your knapsack has size S, you would expect 2k different sums in an interval $S-k\cdot 2^{-n}, S+k\cdot 2^{-n}]$, in other words calculating sums with a precision of $k\cdot 2^{-n}$ isn't enough to give the optimal sum.

With random integers, you can find an optimal sum because of the $2^n$ possible sums, there will be gazillions getting the same result. You wouldn't be able to list all choices that fill the knapsack exactly because there are to many of them, but you can find one.

You can most likely solve the problem "find items that fit in the knapsack, and have a total size at most eps less than the optimal size".

Answer 2

I don't know if you read the book

Algorithm Design - Jon Kleinberg, Eva Tardos

you can read this(at Extension: The Knapsack Problem pag 271) :

Using this recurrence, we can write down a completely analogous dynamic programming algorithm, and this implies the following fact

Thats help to maintain the pseudopolinomial time in $\Theta(nW)$ time.

You have other resource about knapsack - approximation in the book, that maybe can help you.

I hope that help.