В одной широко известной конторе встретился с интересной задачей. Судя по всему — решил неоптимально, или вовсе неверно.

Суть задачи такая: есть функция f(x), определенная на промежутке от 0 до z. Функция является композицией f(x) = k1*g(x) + k2*h(x) + ... + kN*q(x), k1, k2 — коэффициенты, g(x), h(x), ... — нормальные распределения с разными мат. ожиданиями в пределах (0, z), дисперсия — одинакова.

Нужно найти такие дискретные значения x, при которых сумма SUM(f(x)) на промежутке (0, z) будет максимальна. При этом дополнительное условие — на любом отрезке (a, b) не должно быть больше r точек.

Для случая, когда все коэффициенты k кроме k1 равны нулю, получается, что f(x) = k1*g(x), и в этом случае все просто — ставим на "горбе" функции g(x) r точек (поскольку нет условия, что x должны различаться)), после чего сдвигаемся на дистанцию (b-a) влево/вправо, там снова ставим r точек и так далее, пока не дойдем до краев (0, z).

Но если f(x) имеет много максимумов — все становится не так тривиально. Я сходу предложил такой способ: выбирать каждый раз один максимум, куда будут проставлены r точек, после чего этот максимум удаляется, заменяясь на два других локальных максимума (слева и справа). Видимо, ошибся, потому что после этого обсуждения не последовало.

А что думают уважаемые алгоритмики RSDN?