Polynomial\Pseudo-Polynomial Algorithm for Subset-Sum Problem with float and target sum or nearest sum to the target sum

Question

I want to know that is there exist an algorithm to calculate "all possible combinations" of a sorted list (float and duplicates allowed) with a target sum and if there isn't any combination equal to the target sum, the algorithm return "all possible combinations" of nearest sum (lower bound) to the target sum in polynomial or pseudo-polynomial time. I checked Balsub Algorithm "Linear Time Algorithms for Knapsack Problems with Bounded Weights" and also "A Faster Pseudopolynomial Time Algorithm for Subset Sum" with polynomial time but I'm not sure whether these problems are same regarding time-complexity.

This is an example:

Sorted List: {1.5, 2.25, 3.75, 3.81} Target = 3.79 Results: {1.5, 2.25}, {3.75} = 3.75

Thanks

Answer 1

Not that I know of.

The idea of the usual pseudopolynomial solution for subset sum with small integers is that while there are a very large number of combinations, there are relatively few sums to consider. So I can store, by subset sum, a list of which last index and value we arrived at that sum at. I can then find my target answer, and walk the data structure backwards to create a list of the intermediate subset sums and index+values which were on the way to the final target answer. That gives us a data structure that represents a finite state machine to produce all possible answers. We can walk it forward with dynamic programming to either produce one answer, or a count of answers, or recursively enumerate it to give all answers. (Knowing that all answers is usually a very long list.)

The problem with floating point is that now there are a very large number of subsets AND a very large number of intermediate sums. That trick doesn't work. You can round numbers off into buckets, and produce approximate answers that are close to your target. But they will be approximate, and the right answer remains a needle in a haystack.

Sorry.