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

Версия 17:33, 20 декабря 2012

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

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