подбор слагаемых для поиска суммы | |
---|---|
346 Сообщений: 142 Откуда: Ростовская обл. Дата регистрации: 08.09.2006 |
Доброго всем дня!
Есть следующая задача: некоторое кол-во слагаемых из которых необходимо подобрать слагаемые на определенную сумму или как можно ближе к ней. подобранная сумма должна быть равна заданной или меньше,но как можно ближе к заданной. чем то похожа на задачу о перестановках, но мне кажется сложнее. пример: есть слагаемые 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 наиболее оптимальный вариант определяем разницей "заданная сумма" минус "подобранная сумма" чем меньше разница тем оптимальней выбранная комбинация. если разница нуль подбор останавливаем.результат достигнут. у кого какие идеи? математики есть? |
Re: подбор слагаемых для поиска суммы | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
На первый взгляд, алгоритм такой:
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 - не годится Последнее число - не годится Осталось перевести в код. |
Re: подбор слагаемых для поиска суммы | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
|
Re: подбор слагаемых для поиска суммы | |
---|---|
346 Сообщений: 142 Откуда: Ростовская обл. Дата регистрации: 08.09.2006 |
Указанный вами алгоритм не всегда находит оптимальный набор слагаемых... Пользуюсь примерно таким же но, находил лучшие варианты которые при выполнении программа не находит.
|
Re: подбор слагаемых для поиска суммы | |
---|---|
346 Сообщений: 142 Откуда: Ростовская обл. Дата регистрации: 08.09.2006 |
forum.foxclub.ru
может быть, может быть, но это не решение,а рассуждения... подумаю, может еще кто что подскажет?... |
Re: подбор слагаемых для поиска суммы | |
---|---|
Igor Korolyov Автор Сообщений: 34580 Дата регистрации: 28.05.2002 |
Дык решение и есть в часности "метод ветвей и границ" - вполне алгоритмическое - уж на фокс закодировать сам смог бы
Кроме того обычно такую задачу не ограничивают подбором ОДНОЙ суммы - т.е. на практике нужно раскидать для множества сумм (скажем 500 "слагаемых" и 100 "сумм") - а тут критерий оптимальности может быть совсем другим - ибо если для первых 50 "отклонение" будет всего-то 1-2 единицы, а для последних 50 будет по 20 единиц - это может быть не так хорошо, как если бы для всех 100 сумм отклонение составило в среднем 5 единиц... Это я к тому, что возможно ты не ту задачу решаешь, точнее неверно решил, что её можно "разбить" на последовательность более простых задач... ------------------ WBR, Igor |
© 2000-2024 Fox Club  |