Динамическое программирование

[AntiInt]

Решить методом динамического программирования задачу:

$z = x^1x^2 \dots x^n \to \max$
$x^1+x^2+...+x^n = a$
$a>0$

Вот, основные вопросы:
1)каким методом динамич.программирования, их же много, может подскажите, каким из них.
2) как вообще такое решается

[karlicos]

Не знаю, куда здесь можно приткнуть ДП. Но сумма $x^1 \dots x^n = \sum\limits_{k=1}^n x^k = \frac{x^n-1}{x-1} - 1 = a$. Ну а $ z = x^{\frac{n(n-1)}{2}}$ А тут уже можно использовать какой-нибудь численный метод, найти все корни и просто найти максимум.

[venco]

karlicos в сообщении #399381 писал(а):

Не знаю, куда здесь можно приткнуть ДП.

Аналогично.

[Zealint]

Мне почему-то кажется, что автор неверно сформулировал задачу. Если степени поменять на нижние индексы, то уже на что-то похоже. Хотя тогда и ответ слишком очевиден.

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

Решается такое очень просто. Без ДП.
Целевая функция у Вас произведение? (В надежде, что x^i это у Вас i-тая переменная, а не $x^i$)
Стало быть, она равна среднему геометрическому всех переменных в n-ной степени.
А ограничение у Вас - среднее арифметическое, умноженное на n.
Среднее геометрическое не больше среднего арифметического, и равно, если только все усредняемые равны. Поскольку среднее арифметическое у Вас постоянно - то максимум среднего геометрического равен среднему арифметическому.
Стало быть, $x_i=a/n$

-- Чт янв 13, 2011 20:04:06 --

Ну, а если всё же степени одной переменной...
То решаем уравнение $x+x^2+x^3+...+x^n=a$
Берём максимальный корень... Он и есть решение. Но ДП тут совсем уж ни при чём.

[AntiInt]

Ну вот я в такой же делеме: как решить это без ДП я знаю, а как сюда воткнуть ДП - понятия не имею:( хотя задание стоить именно так: решить методом ДП.

[ewert]

Это не степени, естественно, это именно индексы. В конце концов, так даже грамотнее (ибо вектор -- контравариантен), просто обычно индексы для удобства опускают вниз. Но когда дело доходит до итерационных процедур -- выгоднее бывает снова поднять их вверх, т.к. иначе они начинают толкаться с номерами итераций.

[MOEVM]

Поподробней бы задачу изложить