#algorithm #dynamic-programming #intervals
#алгоритм #динамическое программирование #интервалы
Вопрос:
Я довольно долго пытался решить эту проблему проектирования, но застрял в нескольких предположениях. Проблема формулируется как :
Вы заядлый читатель художественной литературы, но вы читаете только одну художественную книгу за раз. Для данной книги i вы можете точно предсказать количество удовольствия ei, которое вы получите от чтения книги, и сколько времени у вас уйдет на чтение этой книги ri. Время начинается с 0. Вы также знаете, что во время ti выйдет фильм, основанный на книге i. Если вы не дочитаете книгу i до времени ti, ваше удовольствие от этой книги упадет до отрицательной бесконечности, поскольку вы не сможете избежать спойлеров, и это будет бесконечно раздражать вас. Учитывая коллекцию из n книг, описанных параметрами ei; ri; ti, ваша цель — составить план — какое подмножество книг читать и когда — чтобы максимизировать общее удовольствие. Предположим, что книги уже отсортированы по неубывающему времени выхода фильмов, т. Е. t1 <= t2 <= .. <= tn. Кроме того, предположим, что все входные числа являются целыми положительными числами. Разработайте алгоритм динамического программирования для этой задачи, который выполняется за время O (n max ti).
Что я пробовал:i. Я попытался рассчитать время завершения fi = ti — ri и применить самое раннее время завершения к интервалам.
ii. Рассчитал соотношение веса (развлечения) / fi, отсортировал в порядке убывания и выбрал лучшее.
iii. Сортируется ti в соответствии с ti и развлечением конкретной книги i, добавляя их в набор решений. До сих пор я не нашел ни одного оптимального решения.
Я понял, что это проблема планирования взвешенных интервалов, но запутался в том, как я могу отсортировать заданные интервалы, чтобы найти оптимальное решение.
Комментарии:
1. Эта проблема слабо сложна (в основном обобщает рюкзак), поэтому сортировка и выполнение чего-то жадного вряд ли приведут вас к чему-либо.
2. итак, по вашему мнению, какой подход @DavidEisenstat лучше всего подходит здесь?
3. Динамическое программирование. Из времени выполнения можно сделать вывод, что состояния DP, вероятно, должны иметь временную составляющую.
Ответ №1:
Позвольте f(t, i) представить максимальное достижимое удовольствие, учитывая первые i книги, где последняя выбранная книга завершена вовремя t . Заполните пробелы:
f(t, 0) ->
<fill>;
f(t, i) when (t > ti) ->
<fill>;
f(t, i) ->
max(
% Read book i
ei f(t - <fill>, i - <fill>),
% Don't read book i
f(<fill>, i - <fill>)
).
Обратите внимание, что «когда последняя выбранная книга будет завершена вовремя t «, это не означает i , что книга th будет прочитана последней, просто мы рассмотрели до i книги th.