2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Помогите с формулой Беллмана
Сообщение30.11.2011, 07:15 
Помогите, пожалуйста, построить рекуррентную формулу Беллмана для максимизации линейной формы:
$$L_{N}{\left(x\right)}=-\sum\limits_{i=1}^{N}{a_{i}\left(1-x_{i}\right)}$$

 
 
 
 Re: Помогите с формулой Беллмана
Сообщение30.11.2011, 15:51 
наверное нужны ограничения? В какой области задача?

 
 
 
 Re: Помогите с формулой Беллмана
Сообщение01.12.2011, 09:00 
Задача в области информационных технологий.
Ограничения:$$\begin{cases}
a_i > 0,\\
x_{i} \in \lbrace 0,\:1 \rbrace ,\\
\sum\limits_{i=1}^{N}{x_i} \leq z.
\end{cases}$$

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

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

 
 
 
 Re: Помогите с формулой Беллмана
Сообщение19.12.2011, 11:02 
Аватара пользователя
Я не очень уверен, что здесь получится применить метод динамического программирования, поскольку последнее условие дает некоторое совместное ограничение на все переменные $x_i$ в совокупности. В зависимости от того, как мы уже задали часть из них, для оставшихся у нас могут быть разные варианты.

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

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

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

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group