Динамическое программирование для задачи о рюкзаке/Задачи/workaholic — различия между версиями

Версия 14:54, 17 декабря 2013

Каждый день можно выбирать между

Перед днем тяжелой работы требуется день отдыхать, то есть, если работать день , то нужно отдыхать день .

Если день делать легкую работу, то в день можно делать любую работу или отдыхать. В первый день не разрешается делать тяжелую работу.

Цель, разумеется, выполнить максимальный объем работ.

Простой жадный алгоритм для этой задачи будет сравнивать с .
- Если тяжелая работа выгоднее, тогда отдыхаем день и выполняем тяжелую в , иначе выполняем легкую.
- Затем рассматриваем день.

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

Разработайте оптимальный полиномиальный алгоритм, чтобы найти максимальный объем работ за дней, когда известны () для каждого дня.

@@ Строка 14: / Строка 14: @@
 ** Затем рассматриваем <m>i + 2</m> день.
-Приведите пример входных данных (<m>h, l</m>), когда алгоритм дает неоптимальное решение.
+Покажите, что для любого $k$, можно представить входные данные <m>h, l</m>, на которых жадный алгоритм выдаст в <m>k</m> раз худшее решение.
 * Разработайте оптимальный полиномиальный алгоритм, чтобы найти максимальный объем работ за <m>n</m> дней, когда известны (<m>l_1,..,l_n; h_2,..,h_n</m>) для каждого дня.
 [[Category:Нерешенные задачи]]