Не удалось настроить динамическое программирование

Question

«Это приближается к концу семестра, и у вас есть n окончательных проектов. Ваша цель, конечно же, состоит в том, чтобы максимизировать ваш общий уровень по этим проектам! Для простоты скажите, что у вас есть всего H часов (положительное целое число) для совместной работы над проектами, и вы потратите целое количество часов на каждый проект.

Чтобы выяснить, как лучше всего разделить ваше время, вы пришли с набором неубывающей оценки функции {e1, e2, ..., en}, по одному для каждого проекта: если вы тратите h часов на проект i (где 0 < = h < = H), вы получите класс ei (h) по этому проекту.

Дайте динамический алгоритм программирования, который принимает оценочные функции {e1,. , , , en} как входной и , который генерирует неотрицательные числа часов {h1,. , , , hn} такие, что (h1 + h2 + ··· + hn) = H и ваш общий класс (e1 (h1) + e2 (h2) + ··· + en (hn)) максимален. Для полных оценок оправдайте свое повторение и кратко проанализируйте время работы вашего алгоритма. »

Answer 1

Это звучит подозрительно, как проблема с резанием журналов, как описано cormen во введении к алгоритмам. Если у вас его нет, я предлагаю его собрать вверх.

Вот один онлайн справочник, хотя я уверен, что вы можете найти другие. http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/

Answer 2

Я считаю, что проблема может быть решена следующим образом.

пространство состояний динамической программы моделируется как n+1 -tupl es (h,h1,...hn) такой, что данный h часов в целом, e1(h1)+...+en(hn) максимальный. Для инициализации задайте значения состояний e1(0),...,en(0), где h=0 (это значение, предположительно, равно 0, как явно не указано иначе).

Затем переведите более h в порядке возрастания; интуитивно, поскольку h incerases, вы разрешаете одной единице больше времени на решение. Поскольку функции полезности e1,...,en монотонно увеличиваются, проблема заключается в том, чтобы решить, где следует потратить лишнюю единицу времени. Это означает, что для h+1 значения (h+1,h1+1,h2,...,hn),...,(h+1,h1,h2,...,hn+1) должны быть оценены e1,...en; выбор максимального значения должен быть сохранен.

В конце концов, последний кортеж (для h=H) дает результат.