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