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

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

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|.

S>Нашел. Для максимального по модулю вылета (и ограничении снизу 0-м) годится оценка в |Х|+|mах(-ai)|+|max(ai)|. То есть сумма модуля максимально отрицательного элемента и максимального положительного.

Спасибо, Дмитрий.
У меня получилось решить с помощью прямого и обратного поиска — вначале строил какие комбинации можно получить от X а потом от 0 — дало прирост скорости в 2 раза.