dynamic-programming
Выбор взвешенной активности
Поиск…
Алгоритм взвешенного планирования работы
Алгоритм взвешенного планирования работы также можно обозначить как алгоритм выбора взвешенной активности.
Проблема в том, что с заданными заданиями с указанием времени начала и окончания времени и прибыль, которую вы делаете, когда вы заканчиваете работу, какова максимальная прибыль, которую вы можете сделать, если нет двух заданий, может выполняться параллельно?
Это выглядит как «Выбор действия», используя «Жадный алгоритм», но есть еще один поворот. То есть вместо максимизации количества завершенных заданий мы сосредоточимся на получении максимальной прибыли. Количество выполненных заданий здесь не имеет значения.
Давайте посмотрим на пример:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | A | B | C | D | E | F |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (2,5) | (6,7) | (7,9) | (1,3) | (5,8) | (4,6) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 6 | 4 | 2 | 5 | 11 | 5 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Работы обозначаются именем, временем начала и окончания и прибылью. После нескольких итераций мы можем узнать, выполняем ли мы Job-A и Job-E максимальную прибыль 17. Теперь, как найти это, используя алгоритм?
Первое, что мы делаем, - сортировать задания по времени окончания в неубывающем порядке. Почему мы это делаем? Это потому, что, если мы выберем задание, которое занимает меньше времени, то мы оставляем самое большое количество времени для выбора других заданий. У нас есть:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
У нас будет дополнительный временный массив Acc_Prof размером n (здесь n обозначает общее количество заданий). Это будет содержать максимальную накопленную прибыль от выполнения заданий. Не понял? Подождите и смотрите. Мы будем инициализировать значения массива с прибылью каждого задания. Это означает, что Acc_Prof [i] сначала получит прибыль от выполнения i-й работы.
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Теперь давайте обозначим позицию 2 с i , а положение 1 обозначим через j . Наша стратегия будет состоять в повторении j от 1 до i-1, и после каждой итерации мы увеличим i на 1, пока i не станет n + 1 .
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Мы проверяем, перекрываются ли задания [i] и Job [j] , то есть, если время окончания работы [j] больше, чем время запуска Job [i] , то эти два задания не могут быть выполнены вместе. Однако, если они не перекрываются, мы проверим, есть ли Acc_Prof [j] + Profit [i]> Acc_Prof [i] . Если это так, мы обновим Acc_Prof [i] = Acc_Prof [j] + Profit [i] . То есть:
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
Здесь Acc_Prof [j] + Profit [i] представляет собой накопленную прибыль от выполнения этих двух заданий. Давайте проверим это для нашего примера:
Здесь Job [j] перекрывается с Job [i] . Таким образом, это невозможно сделать вместе. Так как наш j равен i-1 , мы увеличиваем значение i до i + 1 , равное 3 . И сделаем j = 1 .
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Теперь Job [j] и Job [i] не перекрываются. Общая сумма прибыли, которую мы можем сделать, выбрав эти два задания: Acc_Prof [j] + Profit [i] = 5 + 5 = 10, что больше, чем Acc_Prof [i] . Поэтому мы обновляем Acc_Prof [i] = 10 . Мы также увеличиваем j на 1. Получаем,
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Здесь Job [j] перекрывается с Job [i], а j также равно i-1 . Поэтому мы увеличиваем i на 1 и делаем j = 1 . Мы получаем,
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Теперь Job [j] и Job [i] не перекрываются, мы получаем накопленную прибыль 5 + 4 = 9 , которая больше Acc_Prof [i] . Мы обновляем Acc_Prof [i] = 9 и увеличиваем j на 1.
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 9 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Опять Job [j] и Job [i] не перекрываются. Накопленная прибыль равна: 6 + 4 = 10 , что больше, чем Acc_Prof [i] . Мы снова обновляем Acc_Prof [i] = 10 . Мы увеличиваем j на 1. Получаем:
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 10 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Если мы продолжим этот процесс, после повторения всей таблицы с помощью i наша таблица будет выглядеть следующим образом:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 14 | 17 | 8 |
+-------------------------+---------+---------+---------+---------+---------+---------+
* Несколько шагов были пропущены, чтобы сделать документ короче.
Если мы итерации через массив Acc_Prof , мы можем узнать, что максимальная прибыль равна 17 ! Псевдокод:
Procedure WeightedJobScheduling(Job)
sort Job according to finish time in non-decreasing order
for i -> 2 to n
for j -> 1 to i-1
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
endfor
endfor
maxProfit = 0
for i -> 1 to n
if maxProfit < Acc_Prof[i]
maxProfit = Acc_Prof[i]
return maxProfit
Сложность заполнения массива Acc_Prof равна O (n 2 ). Обход массива принимает O (n) . Таким образом, общая сложность этого алгоритма равна O (n 2 ).
Теперь, если мы хотим узнать, какие задания были выполнены для получения максимальной прибыли, нам нужно пройти массив в обратном порядке, и если Acc_Prof соответствует maxProfit , мы будем вызывать имя задания в стеке и вычитать прибыль эта работа от maxProfit . Мы будем делать это до нашего maxProfit> 0 или мы достигнем начальной точки массива Acc_Prof . Псевдокод будет выглядеть так:
Procedure FindingPerformedJobs(Job, Acc_Prof, maxProfit):
S = stack()
for i -> n down to 0 and maxProfit > 0
if maxProfit is equal to Acc_Prof[i]
S.push(Job[i].name
maxProfit = maxProfit - Job[i].profit
endif
endfor
Сложность этой процедуры: O (n) .
Помните, что если есть несколько графиков работы, которые могут дать нам максимальную прибыль, мы можем найти только один график работы с помощью этой процедуры.