Помогите с формулой Беллмана

[b322730]

Помогите, пожалуйста, построить рекуррентную формулу Беллмана для максимизации линейной формы:

$$L_{N}{\left(x\right)}=-\sum\limits_{i=1}^{N}{a_{i}\left(1-x_{i}\right)}$$

[sergei1961]

наверное нужны ограничения? В какой области задача?

[b322730]

Задача в области информационных технологий.
Ограничения:

$$\begin{cases} a_i > 0,\\ x_{i} \in \lbrace 0,\:1 \rbrace ,\\ \sum\limits_{i=1}^{N}{x_i} \leq z. \end{cases}$$

[Евгений Машеров]

Такое ощущение, что речь о задача динамического программирования. Но тогда хорошо бы уточнить постановку. А то в этой как-то малость тривиально.
В записанной постановке максимизация описанной функции эквивалентна максимизации $\Sigma a_i x_i$, и очевидно, что надо сколь возможно увеличивать $x_i$ при максимальных $a_i$, а учитывая ограничения на х - делать их все равными 1, начиная с i такого, что $a_i$ максимально, и переходя к меньшим, пока сумма $x_i$ не превысит z (тогда последнее надо взять меньшим единицы так, чтобы сумма в точности равнялась z)
Но как-то не верится, что задача столь проста.

[b322730]

Уважаемый Евгений Машеров, а Вы уверены, что подходящим здесь является именно "жадный" алгоритм? Мне бы хотелось именно рекуррентные формулы Беллмана. Или хотя бы описание процесса их порождения, а то его я нигде не могу найти.

[PAV]

Я не очень уверен, что здесь получится применить метод динамического программирования, поскольку последнее условие дает некоторое совместное ограничение на все переменные $x_i$ в совокупности. В зависимости от того, как мы уже задали часть из них, для оставшихся у нас могут быть разные варианты.

Вообще задача устная. По сути, если отбросить все что тут накручено, у нас есть $N$ положительных чисел, из которых нужно выбрать $z$ так, чтобы их сумма была максимальна. Очевидно, что нужно брать $z$ максимальных.

Впрочем, кажется принцип Беллмана тут можно прикрутить, если последовательно наращивать количество единиц от одной до $z$. Но это откровенное извращение.

[b322730]

Уважаемый PAV, очень Вас прошу, помогите, пожалуйста, "прикрутить" сюда эту формулы. Очень очень надо. Внимательно читал соответствующий раздел Акулича и не понял.
Я не прошу готового решения, просто объясните "что" и "как".
Пожалуйста.