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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 18: Строка 18:
 
* Разработайте оптимальный полиномиальный алгоритм, чтобы найти максимальный объем работ за <m>n</m> дней, когда известны (<m>l_1,..,l_n; h_2,..,h_n</m>) для каждого дня.
 
* Разработайте оптимальный полиномиальный алгоритм, чтобы найти максимальный объем работ за <m>n</m> дней, когда известны (<m>l_1,..,l_n; h_2,..,h_n</m>) для каждого дня.
  
[[Category:На проверку]]
+
[[Category:Решенные задачи]]
 
+
 
+
===Остапенко Максим, 975 группа.===
+
 
+
==1) Пример:==
+
 
+
l = {1, 1, 1, 1}
+
 
+
h = {-, 10, 20k, 10}
+
 
+
Решение жадного алгоритма: 20 :  {отдых, <m>h_{2}</m>, отдых, <m>h_{2}</m>}
+
 
+
Оптимальное решение: 20k + 2 :  {<m>l_{1}</m>, отдых, <m>h_{3}</m>,<m>l_{4}</m>}
+
 
+
 
+
==2) Алгоритм: MaxEff(n)==
+
 
+
 
+
 
+
Алгоритм основан на методе динамического программирования:
+
 
+
* Для первых трех дней тривиально устанавливаем решение.
+
 
+
Для последующих дней (пусть номер текущего дня равен <m>i</m>)
+
 
+
* Выполняем MaxEff(i - 3), т.е ищем лучшее решение для дня <m>i-3</m> дней.
+
 
+
* Далее:
+
1) Если в день <m>i - 1</m> выполнялась легкая работа:
+
* Сравнить <m>l_{i}</m> +<m>l_{i-1}</m> и <m>h_{i}</m>. Если первое больше, то просто выполняем легкую работу в день <m>i</m>, иначе меняем день <m>i - 1</m> на отдых и делаем трудную работу в день <m>i</m>.
+
2) Если в день <m>i - 1</m> выполнялась трудная работа:
+
* Сравнить <m>l_{i-2}</m> +<m>h_{i}</m> и <m>h_{i-1}</m> +<m>l_{i}</m>. Если первое больше, то меняем <m>i-2</m> день на легкую работу (до этого был отдых), <m>i-1</m> день на отдых (была тяжелая работа) и делаем в день <m>i</m> тяжелую работу. В противном случае просто делаем легкую работу в день <m>i</m>.
+
 
+
Стоит отметить, что по построению алгоритма, в <m>i-1</m> день нам никогда не встретится отдых.
+
Таким образом, исходя из оптимальность решения для <m>i-3</m> дней и выбора максимума для остальных трех, получим оптимальное решение для <m>i</m> дней.
+
 
+
==3) Сложность:==
+
 
+
Нетрудно заметить, что для любого <m>n</m>, сложность построения алгоритма <m>T(n)</m> равна <m>T(n-3) + C</m>. Так как <m>T(1)</m>, <m>T(2)</m> и <m>T(3)</m> - константы, то сложность <m>T(n)</m> равна <m>O(n)</m>.
+

Версия 21:19, 24 декабря 2014

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

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

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

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

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

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

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

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