Динамическое программирование для задачи о рюкзаке/Задачи/workaholic — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | Каждый день можно выбирать между отдыхом, легкой работой <m>l_i \ge 0</m> или тяжелой работой <m>h_i \ge 0</m> | + | Каждый день можно выбирать между |
| + | * отдыхом, | ||
| + | * легкой работой <m>l_i \ge 0</m> | ||
| + | * или тяжелой работой <m>h_i \ge 0</m>. | ||
| − | + | Перед днем тяжелой работы требуется день отдыхать, то есть, если работать день <m>i</m>, то нужно отдыхать день <m>i-1</m>. | |
| − | * Разработайте полиномиальный алгоритм, чтобы найти максимальный объем работ за <m>n</m> дней, когда известны (<m>l_1,..,l_n; h_2,..,h_n</m>) для каждого дня. | + | Если день <m>i</m> делать легкую работу, то в <m>i-1</m> день можно делать любую работу или отдыхать. В первый день не разрешается делать тяжелую работу. |
| + | |||
| + | Цель, разумеется, выполнить максимальный объем работ. | ||
| + | |||
| + | * Простой жадный алгоритм для этой задачи будет сравнивать <m>h_{i+1}</m> с <m>l_i + l_{i+1}</m>. | ||
| + | ** Если тяжелая работа выгоднее, тогда отдыхаем день <m>i</m> и выполняем тяжелую в <m>i + 1</m>, иначе выполняем легкую. | ||
| + | ** Затем рассматриваем <m>i + 2</m> день. | ||
| + | |||
| + | Приведите пример входных данных (<m>h, l</m>), когда алгоритм дает неоптимальное решение. | ||
| + | |||
| + | * Разработайте оптимальный полиномиальный алгоритм, чтобы найти максимальный объем работ за <m>n</m> дней, когда известны (<m>l_1,..,l_n; h_2,..,h_n</m>) для каждого дня. | ||
[[Category:Нерешенные задачи]] | [[Category:Нерешенные задачи]] | ||
Версия 14:50, 17 декабря 2013
Каждый день можно выбирать между
- отдыхом,
- легкой работой
- или тяжелой работой .
Перед днем тяжелой работы требуется день отдыхать, то есть, если работать день , то нужно отдыхать день .
Если день делать легкую работу, то в день можно делать любую работу или отдыхать. В первый день не разрешается делать тяжелую работу.
Цель, разумеется, выполнить максимальный объем работ.
- Простой жадный алгоритм для этой задачи будет сравнивать с .
- Если тяжелая работа выгоднее, тогда отдыхаем день и выполняем тяжелую в , иначе выполняем легкую.
- Затем рассматриваем день.
Приведите пример входных данных (), когда алгоритм дает неоптимальное решение.
- Разработайте оптимальный полиномиальный алгоритм, чтобы найти максимальный объем работ за дней, когда известны () для каждого дня.