Динамическое программирование для задачи о рюкзаке/Задачи/workaholic — различия между версиями
StasFomin (обсуждение | вклад) |
|||
| Строка 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>. | ||
Версия 11:59, 1 декабря 2014
Каждый день можно выбирать между
- отдыхом,
- легкой работой
- или тяжелой работой .
Перед днем тяжелой работы требуется день отдыхать, то есть, если работать день , то нужно отдыхать день .
Если день делать легкую работу, то в день можно делать любую работу или отдыхать. В первый день не разрешается делать тяжелую работу.
Цель, разумеется, выполнить максимальный объем работ.
- Простой жадный алгоритм для этой задачи будет сравнивать с .
- Если тяжелая работа выгоднее, тогда отдыхаем день и выполняем тяжелую в , иначе выполняем легкую.
- Затем рассматриваем день.
Покажите, что для любого $k$, можно представить входные данные , на которых жадный алгоритм выдаст в раз худшее решение.
- Разработайте оптимальный полиномиальный алгоритм, чтобы найти максимальный объем работ за дней, когда известны () для каждого дня.
Остапенко Максим, 975 группа.
1) Пример:
l = {1, 1, 1, 1}
h = {-, 10, 20k, 10}
Решение жадного алгоритма: 20 : {отдых, , отдых, }
Оптимальное решение: 20k + 2 : {, отдых, ,}
2) Алгоритм: MaxEff(n)
Алгоритм основан на методе динамического программирования:
- Для первых трех дней тривиально устанавливаем решение.
Для последующих дней (пусть номер текущего дня равен )
- Выполняем MaxEff(i - 3), т.е ищем лучшее решение для дня дней.
- Далее:
1) Если в день выполнялась легкая работа:
- Сравнить + и . Если первое больше, то просто выполняем легкую работу в день , иначе меняем день на отдых и делаем трудную работу в день .
2) Если в день выполнялась трудная работа:
- Сравнить + и +. Если первое больше, то меняем день на легкую работу (до этого был отдых), день на отдых (была тяжелая работа) и делаем в день тяжелую работу. В противном случае просто делаем легкую работу в день .
Стоит отметить, что по построению алгоритма, в день нам никогда не встретится отдых. Таким образом, исходя из оптимальность решения для дней и выбора максимума для остальных трех, получим оптимальное решение для дней.
3) Сложность:
Нетрудно заметить, что для любого , сложность построения алгоритма равна . Так как , и - константы, то сложность равна .