Полиномиальный \ псевдополиномиальный алгоритм для задачи о подмножестве сумм с плавающей и целевой суммой или ближайшей суммой к целевой сумме

Question

Я хочу знать, что существует алгоритм для вычисления «всех возможных комбинаций» отсортированного списка (допускается использование чисел с плавающей запятой и дубликатов) с целевой суммой, и если нет комбинации, равной целевой сумме, алгоритм вернуть «все возможные комбинации» ближайшей суммы (нижняя граница) к целевой сумме за полиномиальное или псевдополиномиальное время. Я проверил алгоритм Balsub «Алгоритмы линейного времени для задач о ранцах с ограниченными весами», а также «Алгоритм более быстрого псевдополиномиального времени для суммы подмножеств» с полиномиальным временем, но я не уверен, что эти проблемы одинаковы в отношении сложности времени.

Это пример:

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

Спасибо

Answer 1

Не то, что я знаю.

Идея обычного псевдополиномиального решения для подмножества суммы с маленькими целыми числами заключается в том, что, хотя существует очень большое количество комбинаций, существует относительно небольшое количество сумм, которые следует рассмотреть.Таким образом, я могу хранить, по сумме подмножеств, список последних индексов и значений, к которым мы пришли к этой сумме.Затем я могу найти свой целевой ответ и обойти структуру данных назад, чтобы создать список промежуточных сумм подмножеств и значений index +, которые находились на пути к окончательному целевому ответу.Это дает нам структуру данных, которая представляет собой конечный автомат для получения всех возможных ответов.Мы можем продвинуться вперед с помощью динамического программирования, чтобы получить либо один ответ, либо количество ответов, либо рекурсивно перечислить его, чтобы дать все ответы.(Зная, что все ответы обычно очень длинный список.)

Проблема с плавающей запятой состоит в том, что теперь существует очень большое количество подмножеств И очень большое количество промежуточных сумм.Этот трюк не работает.Вы можете округлять числа в ведра и давать приблизительные ответы, близкие к вашей цели.Но они будут приблизительными, и правильный ответ остается иголкой в ​​стоге сена.

Извините.