Динамическое программирование для задачи о рюкзаке/Задачи/workaholic — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
* Разработайте полиномиальный алгоритм, чтобы найти максимальный объем работ за <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:Нерешенные задачи]] |
Версия 07:42, 18 апреля 2013
Каждый день можно выбирать между отдыхом, легкой работой или тяжелой работой . Перед днем тяжелой работы требуется день отдыхать, то есть, если работать день , то нужно отдыхать день . Если день делать легкую работу, то в день можно делать любую работу или отдыхать. В первый день не разрешается делать тяжелую работу.
- Простой жадный алгоритм для этой задачи будет сравнивать с . Если тяжелая работа выгоднее, тогда отдыхаем день и выполняем тяжелую в , иначе выполняем легкую. Затем рассматриваем день. Приведите пример входных данных (), когда алгоритм дает неоптимальное решение.
- Разработайте полиномиальный алгоритм, чтобы найти максимальный объем работ за дней, когда известны () для каждого дня.