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

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 18 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
Каждый день можно выбирать между отдыхом, легкой работой <m>l_i \ge 0</m> или тяжелой работой <m>h_i \ge 0</m>. Перед днем тяжелой работы требуется день отдыхать, то есть, если работать день <m>i</m>, то нужно отдыхать день <m>i - 1</m>. Если день <m>i</m> делать легкую работу, то в <m>i - 1</m> день можно делать любую работу или отдыхать. В первый день не разрешается делать тяжелую работу.
+
Каждый день можно выбирать между
 +
* отдыхом,  
 +
* легкой работой <m>l_i \ge 0</m>  
 +
* или тяжелой работой <m>h_i \ge 0</m>.  
  
−
* Простой жадный алгоритм для этой задачи будет сравнивать <m>h_{i+1}</m> с <m>l_i + l_{i + 1}</m>. Если тяжелая работа выгоднее, тогда отдыхаем день <m>i</m> и выполняем тяжелую в <m>i + 1</m>, иначе выполняем легкую. Затем рассматриваем <m>i + 2</m> день. Приведите пример входных данных (<m>h, l</m>), когда алгоритм дает неоптимальное решение.
+
Перед днем тяжелой работы требуется день отдыхать, то есть, если работать день <m>i</m>, то нужно отдыхать день <m>i-1</m>.  
  
−
* Разработайте полиномиальный алгоритм, чтобы найти максимальный объем работ за <m>n</m> дней, когда известны (<m>l_1,..,l_n; h_2,..,h_n</m>) для каждого дня.
+
Если день <m>i</m> делать легкую работу, то в <m>i-1</m> день можно делать любую работу или отдыхать. В первый день не разрешается делать тяжелую работу.
  
−
[[Category:Решенные задачи]]
+
Цель, разумеется, выполнить максимальный объем работ.
 +
 
 +
* Простой жадный алгоритм для этой задачи будет сравнивать <m>h_{i+1}</m> с <m>l_i + l_{i+1}</m>.
 +
** Если тяжелая работа выгоднее, тогда отдыхаем день <m>i</m> и выполняем тяжелую в <m>i + 1</m>, иначе выполняем легкую.
 +
** Затем рассматриваем <m>i + 2</m> день.
 +
 
 +
Покажите, что для любого $k$, можно представить входные данные <m>h, l</m>, на которых жадный алгоритм выдаст в <m>k</m> раз худшее решение.
 +
 
 +
* Разработайте оптимальный полиномиальный алгоритм, чтобы найти максимальный объем работ за <m>n</m> дней, когда известны (<m>l_1,..,l_n; h_2,..,h_n</m>) для каждого дня.
 +
 
 +
[[Категория:Решенные задачи]]

Версия 15:49, 20 мая 2020

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

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

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

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

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

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

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

  • Разработайте оптимальный полиномиальный алгоритм, чтобы найти максимальный объем работ за дней, когда известны () для каждого дня.
Источник — «https://discopal.ispras.ru/index.php?title=Динамическое_программирование_для_задачи_о_рюкзаке/Задачи/workaholic&oldid=11027»