DAA-마감일이있는 작업 순서 지정

문제 설명

작업 순서 문제에서 목표는 마감일 내에 완료되고 최대 이익을 제공하는 일련의 작업을 찾는 것입니다.

해결책

고려해 보겠습니다. n마감일까지 작업이 완료되면 마감일 및 수익과 관련된 일자리가 주어집니다. 이러한 작업은 최대 이익이있는 방식으로 주문해야합니다.

주어진 모든 작업이 기한 내에 완료되지 않을 수 있습니다.

가정, 기한 i^th 일 J_i 이다 d_i 이 직업에서 얻은 이익은 p_i. 따라서이 알고리즘의 최적 솔루션은 최대 수익으로 실현 가능한 솔루션입니다.

따라서 $ D (i)> 0 $ for $ 1 \ leqslant i \ leqslant n $.

처음에 이러한 작업은 이익에 따라 주문됩니다. 예 : $ p_ {1} \ geqslant p_ {2} \ geqslant p_ {3} \ geqslant \ : ... \ : \ geqslant p_ {n} $.

Algorithm: Job-Sequencing-With-Deadline (D, J, n, k) 
D(0) := J(0) := 0 
k := 1 
J(1) := 1   // means first job is selected 
for i = 2 … n do 
   r := k 
   while D(J(r)) > D(i) and D(J(r)) ≠ r do 
      r := r – 1 
   if D(J(r)) ≤ D(i) and D(i) > r then 
      for l = k … r + 1 by -1 do 
         J(l + 1) := J(l) 
         J(r + 1) := i 
         k := k + 1