# What is the complexity of the time for the backpack with real weights?

Leave $$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$$ its corresponding values.

As is known, the backpack problem for whole weights can be solved by dynamic programming (or, equivalently, using recursion + memory), with a time complexity of $$mathcal O (nW)$$, where $$W$$ is the total weight that our bag can hold, and $$n$$ is the number of elements

However, for real numbered weights, the algorithm fails (just imagine a billion elements with weight $$<1$$Y $$W = 1$$). We can probably round them up in an intelligent way and then scale them up to be whole again, but that would increase the size of the problem in an unacceptable way.

Another approach would be to use recursion instead of dynamic programming, because the idea behind the algorithm still works, be it the $$n$$& # 39; The item is in the optimal solution, or not.

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

we are different, leaving us with $$2 ^ n$$ weight-sums to memorize.

Is there an optimal algorithm that manages to maintain the complexity of pseudo-polynomial time?