PDA

Просмотр полной версии : вопрос знатокам математики


spider-intruder
05.03.2008, 20:58
есть число N
есть множество чисел M

Как !оптимально! представить число N суммой из набора чисел М
(равно или больше)


например есть число 200
надо представить его сумой чисел 3,5,17,23

Интересует не конкретное решение а алгоритм расчета...
Кроме брутфорса есть варианты? если нет то как оптимизировать брутфорс.

Sn@k3
05.03.2008, 21:02
т.е. не четных? ну попробуй делить пока не останеться не делимое число. или складываь отрицательные пока не будет больше=.


Кстати причем у математика? на уровне программирования решаемо

spider-intruder
05.03.2008, 21:04
Вопрос решен!
http://en.wikipedia.org/wiki/Knapsack_problem