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

S>Можно подумать на эту тему, только тогда пожалуйста поподробнее. Какие примерно значения имеют эти дельты и сколько их обычно? Какова величина Х? Каковы временные-железячные требования к алгоритму (если он будет работать за доли секунды на пентиуме, это устроит?) Устроит ли нахождение хорошего, но не вполне оптимального решения или это не годится категорически?

Аффтар, что-то вы молчите. А тут еще явно есть чего покопать, но без каких-то примерных представлений о реально встречающихся в вашей задаче числах это сложно. Рискну все-таки предложить такую оптимизацию, имеющую смысл когда X по модулю много больше дельт. В этом случае, как несложно заметить, сумма будет составлена большим количеством самого большого по модулю слагаемого одного знака с X и некоторым небольшим количеством других слагаемых. Чтобы ускорить поиск, можно применять ту же схему, что и раньше, но при каждом получении нового числа очередной серии смотреть, не является ли разность между этим числом и X кратной самого большого (по модулю) из дельт. Естественно, на очередном шаге может возникнуть одновременно несколько таких чисел и надо брать наибольшее (тогда понадобиться наименьшее количество слагаемых).

Так же хочу поправиться. Ранее я писал:

S>С ограничением по максимуму (какой брать максимальный модуль допустимых чисел) все тоже просто — искомые числа можно получить так, что промежуточные суммы вылетят не более чем на модуль максимального из слагаемых от искомого числа.

Это не верно. Контрпример — возьмем X=1 и a={11 -3}. Схема генерации с минимальным вылетом вверх получается такая (числа в скобках это временная сумма): 11 -3 -3 -3 (2) 11 (13) -3 -3 -3 -3 (1). То есть вылет получается на 13, что больше X+max(ai)=1+11=12. Видно, что сделать вылет меньше нельзя. Вопрос о том, что брать как верхнюю грань, отсекающую лишний поиск, не так прост. Ну, кто сообразит, сколько тут должно быть? Я как следующее предположение рискну выдвинуть |X|+sum|ai|.