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

Материал из DISCOPAL
Перейти к: навигация, поиск

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

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

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

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

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

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

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

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


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

1) Пример:

l = {1, 1, 1, 1}

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

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

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


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

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

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

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

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

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

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

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

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

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

3) Сложность:

Нетрудно заметить, что для любого , сложность построения алгоритма равна . Так как , и - константы, то сложность равна .

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

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

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