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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(Массовая правка: замена :Решенные задачи]] на :Нерешенные задачи]])
Строка 18: Строка 18:
 
* Разработайте оптимальный полиномиальный алгоритм, чтобы найти максимальный объем работ за <m>n</m> дней, когда известны (<m>l_1,..,l_n; h_2,..,h_n</m>) для каждого дня.
 
* Разработайте оптимальный полиномиальный алгоритм, чтобы найти максимальный объем работ за <m>n</m> дней, когда известны (<m>l_1,..,l_n; h_2,..,h_n</m>) для каждого дня.
  
[[Категория:Решенные задачи]]
+
[[Категория:Нерешенные задачи]]

Версия 20:59, 20 сентября 2018

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

  • отдыхом,
  • легкой работой
  • или тяжелой работой .

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

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

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

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

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

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