Доброго всем дня!
Есть следующая задача:
некоторое кол-во слагаемых из которых необходимо подобрать слагаемые на определенную сумму или как можно ближе к ней.
подобранная сумма должна быть равна заданной или меньше,но как можно ближе к заданной.
чем то похожа на задачу о перестановках, но мне кажется сложнее.
пример:
есть слагаемые
1.=10
2.=5
3.=6
4.=11,5
5.=0,95
6.=15
подобрать слагаемые на сумму 12
из указанных слагаемых оптимальные 5+6+0,95=11,95 или 11,5+0=11,5
наиболее оптимальный вариант определяем разницей "заданная сумма" минус "подобранная сумма" чем меньше разница тем оптимальней выбранная комбинация. если разница нуль подбор останавливаем.результат достигнут.

у кого какие идеи? математики есть?

На первый взгляд, алгоритм такой:
1. Сортируем слагаемые по убыванию.
2. Находим первое число, меньшее за заданную сумму.
3. Двигаясь вниз, находим числа, которые при добавлении к первому дают сумму, меньшую за заданную, и так до достижения дна собираем первую сумму.
4. Возвращаемся к началу, и в качестве исходного берем число, следующее за найденным в п.2.
5. Повторяем п.3.
6. Сравниваем сумму с предыдущей, сохраняем лучший вариант.
7. Повторяем 4-6 до достижения конца последовательности.

Т.е. примерно так.
Число 15 игнорируем.
Первая цепочка 11,5 без других слагаемых
Вторая цепочка 10+0,95=10,95 - отбраковываем
Третья цепочка 6+5+0,95=11,95 - отбраковываем первую цепочку
Четвертая цепочка 5+0,95=5,95 - не годится
Последнее число - не годится

Осталось перевести в код.

forum.foxclub.ru

Указанный вами алгоритм не всегда находит оптимальный набор слагаемых... Пользуюсь примерно таким же но, находил лучшие варианты которые при выполнении программа не находит.

forum.foxclub.ru
может быть, может быть, но это не решение,а рассуждения... подумаю, может еще кто что подскажет?...

Дык решение и есть в часности "метод ветвей и границ" - вполне алгоритмическое - уж на фокс закодировать сам смог бы
Кроме того обычно такую задачу не ограничивают подбором ОДНОЙ суммы - т.е. на практике нужно раскидать для множества сумм (скажем 500 "слагаемых" и 100 "сумм") - а тут критерий оптимальности может быть совсем другим - ибо если для первых 50 "отклонение" будет всего-то 1-2 единицы, а для последних 50 будет по 20 единиц - это может быть не так хорошо, как если бы для всех 100 сумм отклонение составило в среднем 5 единиц...
Это я к тому, что возможно ты не ту задачу решаешь, точнее неверно решил, что её можно "разбить" на последовательность более простых задач...