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

Ссылки сюда (11) →

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

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

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

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

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

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

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

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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.