Рекурсивный (?) перебор (?) вариантов.

[GSerg]

Имеется массивчик, чисел так на 500. Задача: отобрать из оного несколько (лучше меньше) чисел так, чтобы их сумма минимально отличалась от некоего заданного числа. Имеется допустимая погрешность: если сумма в рамках оной, то ОК. Из всех сумм "в рамках оной" нужно выбрать ту, у которой число слагаемых меньше.

Спрашивается, как лучше подойти к решению такой задачи? Наглый перебор (сначала для двух слагаемых, потом для трёх...) кажется слишком неоптимальным. Рекурсия - как посмотрю на количество комбинаций (ну, из 500 по 8, к примеру), так сразу начинаю сильно сомневаться в том, что стек выдержит.
Ну и вообще, время выполнения будет ли реальным?
Что скажете?

[Igor_123]

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

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

[GSerg]

Вроде справился...
Бета-тестинг прошёл успешно, хотя был не очень плотным. Так что идеи постите, мало ли что

[Approximator]

Вроде справился...
Бета-тестинг прошёл успешно, хотя был не очень плотным. Так что идеи постите, мало ли что

Дык, на самом деле усё делается просто. Только "шиворот-навыворот".
Берётся сумма, массив упорядочивается (иключаются повторы и для убыстрения делаешь контрольную сумму всех чисел). Сначала вычитается первое наибольшее (если одни и те же числа могут повторяться, то делаешь это максимальное количество раз) (контрольную сумму тоже уменьшаешь).
Затем из разности вычитаешь следующее наибольшее и т.п. В самом критическом случае количество проходов будет
<количество чисел в комбинации>*<количество чисел в массиве>
Но не больше. Мне кажется, что даже 100*500=50000 - ерунда.

Или же, через систему линейных уравнений. Последнее обычно записывать мутрно. Хотя быстрее.