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