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

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

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

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

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

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

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

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

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

Остапенко Максим, 975 группа.

1) Пример:

l = {1, 1, 1, 1}

h = {-, 10, 20k, 10}

Решение жадного алгоритма: 20 : {отдых, , отдых, }

Оптимальное решение: 20k + 2 : {, отдых, ,}

2) Алгоритм: MaxEff(n)

Алгоритм основан на методе динамического программирования:

Для первых трех дней тривиально устанавливаем решение.

Для последующих дней (пусть номер текущего дня равен )

Выполняем MaxEff(i - 3), т.е ищем лучшее решение для дня дней.

Далее:

1) Если в день выполнялась легкая работа:

Сравнить + и . Если первое больше, то просто выполняем легкую работу в день , иначе меняем день на отдых и делаем трудную работу в день .

2) Если в день выполнялась трудная работа:

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

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