MAXimal | |
добавлено: 11 Jun 2008 11:22 Содержание [скрыть] Оптимальный выбор заданий при известных временах завершения и длительностях выполненияПусть дан набор заданий, у каждого задания известен момент времени, к которому это задание нужно завершить, и длительность выполнения этого задания. Процесс выполнения какого-либо задания нельзя прерывать до его завершения. Требуется составить такое расписание, чтобы выполнить наибольшее число заданий. РешениеАлгоритм решения — жадный (greedy). Отсортируем все задания по их крайнему сроку, и будем рассматривать их по очереди в порядке убывания крайнего срока. Также создадим очередь , в которую мы будем постепенно помещать задания, и извлекать из очереди задание с наименьшим временем выполнения (например, можно использовать set или priority_queue). Изначально пустая. Пусть мы рассматриваем -ое задание. Сначала поместим его в . Рассмотрим отрезок времени между сроком завершения -го задания и сроком завершения -го задания — это отрезок некоторой длины . Будем извлекать из задания (в порядке увеличения оставшегося времени их выполнения) и помещать на выполнение в этом отрезке, пока не заполним весь отрезок . Важный момент — если в какой-то момент времени очередное извлечённое из структуры задание можно успеть частично выполнить в отрезке , то мы выполняем это задание частично — именно настолько, насколько это возможно, т.е. в течение единиц времени, а оставшуюся часть задания помещаем обратно в . По окончании этого алгоритма мы выберем оптимальное решение (или, по крайней мере, одно из нескольких решений). Асимптотика решения — . Реализацияint n; vector < pair<int,int> > a; // задания в виде пар (крайний срок, длительность) ... чтение n и a ... sort (a.begin(), a.end()); typedef set < pair<int,int> > t_s; t_s s; vector<int> result; for (int i=n-1; i>=0; --i) { int t = a[i].first - (i ? a[i-1].first : 0); s.insert (make_pair (a[i].second, i)); while (t && !s.empty()) { t_s::iterator it = s.begin(); if (it->first <= t) { t -= it->first; result.push_back (it->second); } else { s.insert (make_pair (it->first - t, it->second)); t = 0; } s.erase (it); } } for (size_t i=0; i<result.size(); ++i) cout << result[i] << ' ';
|