1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It is taken for granted in the question that "pseudo-polynomial" time-complexity in case of real numbers is well-known. However, is it even defined anywhere? It looks like it is non-trivial to define that kind of time-complexity. $\endgroup$ – Apass.Jack Jan 1 at 9:19
1
$\begingroup$

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".

$\endgroup$
  • $\begingroup$ So in other words, there might be an approximation algorithm running in polynomial time, but you doubt the existence of a general algorithm? $\endgroup$ – Sudix Dec 8 '18 at 22:02
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Take the square roots of the numbers from 1 to 1000. Pick a subset such that the sum if ≤ 12,000 but as large as possible. You should find a subset so the sum is within 150 decimal digits of 12,000. What is W? $\endgroup$ – gnasher729 Dec 8 '18 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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