Есть множество чисел. Необходимо выбрать из него некоторое количество (неопределенное) элементов, сумма которых как можно ближе будет к заданому числу.

Здравствуйте, Vider, Вы писали:

V>Есть множество чисел. Необходимо выбрать из него некоторое количество (неопределенное) элементов, сумма которых как можно ближе будет к заданому числу.

Ну точный алгоритм найти вряд ли удастся (ибо это sum of subset problem — известная NP-complete задачка)
Но Вам похоже надо приближенно. Это в принципе можно сделать за полином. Посмотрите здесь (внизу страницы)

Думается мне, что для общего случая, когда числа из R, задача решается только перебором. С другой стороны, если ввести некоторые допущения, можно воспользоваться динамическим программированием. Например, если все числа принадлежат N и число, которое нужно набрать тоже принадлежит N, последовательность рассуждений может быть следующая.

У нас есть множество чисел S = {N1…Nn}. Нам нужно найти индексы i1…ik, такие, что Ni1 + … + Nik даёт максимально близкое к М число. Допустим, что в наш итоговый набор входит число N1. Это значит, что нам нужно набрать максимально близкое число к M – N1, но, не используя первое число. Рекурсивное решение выглядит следующим образом:

Find(D, m)
Max := бесконечность
Foreach n in D
Max_n := Find(D – {n}, m – n) + n
If (|Max_n – m| < Max)
Max = |Max_n – m|

Понятно, что время работы такой функции О(n!). С другой стороны, эта функция легко сводится к динамическому программированию. Мы заполняем таблицу N * M таким образом. MAS[I][J] = максимально близкое число к J, которое можно набрать используя первые I числа из множества. Тогда ответом будет MAS[n][M]. Таблица заполняется последовательно. Для того, чтобы заполнить ячейку MAS[i][j], надо произвести i-1 cравнение. Т.е. сложность алгоритма получается O(M * N^2).