dynamic-programming
Vägt aktivitetsval
Sök…
Viktat jobbplaneringsalgoritm
Viktad jobbplaneringsalgoritm kan också betecknas som viktad aktivitetsval algoritm.
Problemet är, med tanke på vissa jobb med deras starttid och sluttid, och en vinst du gör när du är klar med jobbet, vad är den maximala vinsten du kan göra eftersom inga två jobb kan utföras parallellt?
Den här ser ut som Aktivitetsval med Greedy Algoritm, men det finns en extra twist. Det vill säga, istället för att maximera antalet färdigställda jobb fokuserar vi på att göra maximal vinst. Antalet utförda jobb spelar ingen roll här.
Låt oss titta på ett exempel:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Jobbena har ett namn, deras start- och sluttid och vinst. Efter några iterationer kan vi ta reda på om vi utför Job-A och Job-E , kan vi få maximal vinst på 17. Nu hur kan vi ta reda på detta med hjälp av en algoritm?
Det första vi gör är att sortera jobben efter deras slutbehandlingstid i icke-minskande ordning. Varför gör vi det här? Det beror på att om vi väljer ett jobb som tar mindre tid att avsluta, lämnar vi mest tid för att välja andra jobb. Vi har:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Vi kommer att ha en extra tillfällig matris Acc_Prof av storlek n (Här anger n det totala antalet jobb). Detta kommer att innehålla den maximala ackumulerade vinsten för att utföra jobb. Får du inte det? Vänta och se på. Vi initierar värdena i matrisen med vinsten för varje jobb. Det betyder att Acc_Prof [i] till en början kommer att ha vinsten med att utföra i-th jobb.
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Låt oss nu beteckna position 2 med i , och position 1 kommer att betecknas med j . Vår strategi är att iterera j från 1 till i-1 och efter varje iteration kommer vi att öka i med 1 tills jag blir 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Vi kontrollerar om Job [i] och Job [j] överlappar, det vill säga om sluttiden för Job [j] är större än Job [i] : s starttid, kan dessa två jobb inte göras tillsammans. Men om de inte överlappar varandra kontrollerar vi om Acc_Prof [j] + Vinst [i]> Acc_Prof [i] . Om så är fallet kommer vi att uppdatera Acc_Prof [i] = Acc_Prof [j] + Profit [i] . Det är:
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
Här representerar Acc_Prof [j] + Profit [i] den ackumulerade vinsten för att göra dessa två jobb. Låt oss kolla det för vårt exempel:
Här överlappar Job [j] med Job [i] . Så dessa kan inte göras tillsammans. Eftersom vår j är lika med i-1 , ökar vi värdet på i till i + 1 som är 3 . Och vi gör 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Nu överlappar Job [j] och Job [i] inte. Den totala vinsten vi kan göra genom att välja dessa två jobb är: Acc_Prof [j] + Vinst [i] = 5 + 5 = 10 vilket är större än Acc_Prof [i] . Så vi uppdaterar Acc_Prof [i] = 10 . Vi ökar också j med 1. Vi får,
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Här överlappar Job [j] med Job [i] och j är också lika med i-1 . Så vi ökar i med 1 och gör j = 1 . Vi får,
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Nu överlappar Job [j] och Job [i] inte, vi får den ackumulerade vinsten 5 + 4 = 9 , vilket är större än Acc_Prof [i] . Vi uppdaterar Acc_Prof [i] = 9 och steget j med 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Återigen överlappar Job [j] och Job [i] inte. Den ackumulerade vinsten är: 6 + 4 = 10 , vilket är större än Acc_Prof [i] . Vi uppdaterar igen Acc_Prof [i] = 10 . Vi ökar j med 1. Vi får:
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Om vi fortsätter med denna process, efter att iterera hela tabellen med i , kommer vårt bord äntligen att se ut:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
* Några steg har hoppats över för att göra dokumentet kortare.
Om vi uppdaterar oss genom matrisen Acc_Prof , kan vi ta reda på den maximala vinsten till 17 ! Pseudokoden:
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
Komplexiteten i att fylla i Acc_Prof- matrisen är O (n 2 ). Arrayomgången tar O (n) . Så den totala komplexiteten för denna algoritm är O (n 2 ).
Nu, om vi vill ta reda på vilka jobb som utfördes för att få maximal vinst, måste vi korsa matrisen i omvänd ordning och om Acc_Prof matchar maxProfit , kommer vi att trycka på namnet på jobbet i en stack och subtrahera vinsten av det jobbet från maxProfit . Vi kommer att göra detta tills vår maxProfit> 0 eller så når vi startpunkten för Acc_Prof- arrayen. Pseudokoden kommer att se ut:
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
Komplexiteten i denna procedur är: O (n) .
En sak att komma ihåg, om det finns flera jobbscheman som kan ge oss maximal vinst kan vi bara hitta ett jobbschema via den här proceduren.