Учтите, что у вас есть набор поплавков, например
4.2 ; 2.6 ; 6.9 ; 1.1
И вам нужно определить, существует ли Подмножество, сумма которого равна 5,3, и если да, то вернуть это множество.
Все заданные числа всегда имеют один десятичный знак.
Один из способов сделать это — перебором: сгенерировать все комбинации из исходного набора и проверить сумму каждой по отдельности. Однако это довольно плохо, и обычно такого рода проблемы решаются с помощью динамического программирования --- действительно, это особенность проблема с рюкзаком.
Мой вопрос: поскольку мы рассматриваем поплавки, как бы вы справились с этим эффективно?
Стандартный подход к динамическому программированию не кажется хорошим кандидатом, так как мне потребовалось бы построить таблицу, учитывающую все возможные значения float от 0 до целевого числа (5,3 в этом примере). Поскольку мы знаем, что у нас всегда одна десятичная точка, я думаю, можно представить себе такую таблицу:
0 | 0.1 | 0.2 | ... | 5.3
4.2
2.6
6.9
1.1
но я не думаю, что это будет хорошо масштабироваться... (Здесь 5,3 - это просто значение для простоты, у меня нет информации о целевом значении, связанном на практике.)
Любые мысли о том, как справиться с этим?
