Динамическое программирование для задачи о рюкзаке/Задачи/workaholic — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 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>) для каждого дня. | ||
| − | [[Category: | + | [[Category:Нерешенные задачи]] |
Версия 07:49, 24 апреля 2014
Каждый день можно выбирать между
- отдыхом,
- легкой работой
- или тяжелой работой .
Перед днем тяжелой работы требуется день отдыхать, то есть, если работать день , то нужно отдыхать день .
Если день делать легкую работу, то в день можно делать любую работу или отдыхать. В первый день не разрешается делать тяжелую работу.
Цель, разумеется, выполнить максимальный объем работ.
- Простой жадный алгоритм для этой задачи будет сравнивать с .
- Если тяжелая работа выгоднее, тогда отдыхаем день и выполняем тяжелую в , иначе выполняем легкую.
- Затем рассматриваем день.
Покажите, что для любого $k$, можно представить входные данные , на которых жадный алгоритм выдаст в раз худшее решение.
- Разработайте оптимальный полиномиальный алгоритм, чтобы найти максимальный объем работ за дней, когда известны () для каждого дня.