Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Кстати, обязательно ли оптимальное решение или можно приближенно? 02.09.06 00:02 Число просмотров: 2374
Автор: amirul <Serge> Статус: The Elderman
|
> Приятель попросил помочь. Ему в бизнес-приложении
> необходимо реализовать функцию сопоставления-поиска
> платежей и услуг. Задача сводится к нахождению такого
> подмножества из заданного множества чисел, сумма элементов
> которого ближе всего к заданной величине.
А то, что то мне эта задачка уж сильно напомнила "1d bin packing problem" в народе еще именуюемую задачей оптимальной раскройки одномерного профиля.
Если изначально задача состоит в том, чтобы расфасовать числа по наборам таким образом, чтобы минимизировать количество этих наборов, то можно использовать "Best Fit Decreasing" или "First Fit Decreasing". В случае, если набор не ограничен сверху жестко (как длины отрезаемых профилей), то можно использовать "Best Fit Decreasing", но в качестве целевой функции для определения наилучшести использовать не остаток, а модуль разности.
Время полиномиальное (насколько я понимаю O(N^2) для BFD-решения). Количество наборов не превышает 11/9 OPT + 4 (где OPT - оптимальное количество)
> Быстрее кто-нибудь сможет?
Тут http://en.wikipedia.org/wiki/Bin_packing говорят, что существуют приближенные методы, вычисляющие разбивку С ЛЮБОЙ заданной точностью (процентом от оптимального решения). В частности PTAS (http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme)
|
- Задачка - leo 31.08.06 11:31 [2138]
- Кстати, обязательно ли оптимальное решение или мож... - amirul 02.09.06 00:02 [2374]
- Конечно интересно. - DPP 31.08.06 14:23 [2262]
- Мой код (для MSC) - leo 31.08.06 12:39 [2397]
|
|
|
подробно о проекте
Анализ криптографических сетевых... 
