Xếp việc

Bài 5.2. Xếp việc

           Có N công việc cần thực hiện trên một máy tính, mỗi việc đòi hỏi đúng 1 giờ máy. Với mỗi việc ta biết thời hạn phải nộp kết quả thực hiện sau khi hoàn thành việc đó và tiền thưởng thu được nếu nộp kết quả trước hoặc đúng thời điểm quy định. Chỉ có một máy tính trong tay, hãy lập lịch thực hiện đủ N công việc trên máy tính sao cho tổng số tiền thưởng thu được là lớn nhất và thời gian hoạt động của máy là nhỏ nhất. Giả thiết rằng máy được khởi động vào đầu ca, thời điểm
 t = 0 và chỉ tắt máy sau khi đã hoàn thành đủ N công việc.

Dữ liệu vào: tệp văn bản viec.inp:

-          Dòng đầu tiên là số N.

-          N dòng tiếp theo: mỗi việc được mô tả bằng hai số tự nhiên, số thứ nhất là thời hạn giao nộp, số thứ hai là tiền thưởng. Các số cách nhau bởi dấu cách.

Thí dụ:

viec.inp 4 1 15 3 10 5 100 1 27

Ý nghĩa: Cho biết có 4 việc với các thông tin sau: -       Việc thứ nhất phải nộp không muộn hơn thời điểm 1 (giờ) với tiền thưởng 15 (ngàn đồng); -       Việc thứ hai phải nộp không muộn hơn thời điểm 3 (giờ) với tiền thưởng 10 (ngàn đồng); -       Việc thứ ba phải nộp không muộn hơn thời điểm 5 (giờ) với tiền thưởng 100 (ngàn đồng); -       Việc thứ tư phải nộp không muộn hơn thời điểm 1 (giờ) với tiền thưởng 27 (ngàn đồng).

Dữ liệu ra: tệp văn bản viec.out:

-          N dòng đầu tiên, dòng thứ t ghi một số tự nhiên i cho biết việc thứ i được làm trong giờ t.

-          Dòng cuối cùng ghi tổng số tiền thu được.

Với thí dụ trên, tệp viec.out sẽ như sau:

viec.out 4 2 3 1 137

Ý nghĩa: -    Giờ thứ 1 thực hiện việc 4 và nộp đúng hạn nên được thưởng 27; -    Giờ thứ 2 thực hiện việc 2 và nộp trước hạn nên được thưởng 10; -    Giờ thứ 3 thực hiện việc 3 và nộp trước hạn nên được thưởng 100; -    Giờ thứ 4 thực hiện việc 1; -    Tổng tiền thưởng thu được do đã hoàn thành đúng hạn ba việc 4, 2 và 3 là 27 + 10 + 100 = 137.

Thuật toán

Ta ưu tiên cho những việc có tiền thưởng cao, do đó ta sắp các việc giảm dần theo tiền thưởng. Với mỗi việc k ta đã biết thời hạn giao nộp việc đó là h = t[k]. Ta xét trục thời gian b. Nếu giờ h trên trục đó đã bận do việc khác thì ta tìm từ thời điểm h trở về trước một thời điểm có thể thực hiện được việc k đó. Nếu tìm được một thời điểm m như vậy, ta đánh dấu bằng mã số của việc đó trên trục thời gian b, b[m]:= k. Sau khi xếp việc xong, có thể trên trục thời gian còn những thời điểm rỗi, ta dồn các việc đã xếp về phía trước nhằm thu được một lịch làm việc trù mật, tức là không có giờ trống. Cuối cùng ta xếp tiếp những việc trước đó đã xét nhưng không xếp được. Đây là những việc phải làm nhưng không thể nộp đúng hạn nên sẽ không có tiền thưởng. Với thí dụ đã cho, N = 4, thời hạn giao nộp t = (1, 3, 5, 1) và tiền thưởng a = (15, 10, 100, 27) ta tính toán như sau:

-       Khởi trị: trục thời gian với 5 thời điểm ứng với Tmax = 5 là thờ điểm muôn nhất phải nộp kết quả, Tmax = max { thời hạn giao nộp },  b = (0, 0, 0, 0,0).

-       Chọn việc 3 có tiền thưởng lớn nhất là 100. Xếp việc 3 với thời hạn t[3] = 5 vào h: h[5] = 3. Ta thu được h = (0, 0, 0, 0, 3).

-       Chọn tiếp việc 4 có tiền thưởng 27. Xếp việc 4 với thời hạn t[4] = 1 vào h: h[1] = 4. Ta thu được h = (4, 0, 0, 0, 3).

-       Chọn tiếp việc 1 có tiền thưởng 15. Xếp việc 1 với thời hạn t[1] = 1 vào h: Không xếp được vì từ thời điểm 1 trở về trước trục thời gian h[1..1] đã kín. Ta thu được h = (4, 0, 0, 0, 3).

-       Chọn nốt việc 2 có tiền thưởng 10. Xếp việc 2 với thời hạn t[2] = 3 vào h: h[3] = 2.

-       Ta thu được h = (4, 0, 2, 0, 3).

-       Dồn việc trên trục thời gian h, ta thu được h = (4, 2, 3, 0, 0).

-       Xếp nốt việc phải làm mà không có thưởng, ta thu được h = (4, 2, 3, 1).

-       Ca làm việc kéo dài đúng N = 4 giờ.

-       Nếu không muốn sắp giảm mảng tiền thưởng a theo chỉ dẫn ta có thể sắp song song a và id như mô tả trong chương trình.

Trong chương trình dưới đây ta sử dụng mảng id với hai mục đích: id[i] = v > 0 cho biết việc v đứng thứ i trong dãy được sắp giảm theo giá trị tiền thưởng và việc v chưa được xếp. id[i] = v < 0 cho biết việc v đã xếp xong trong lần duyệt đầu tiên.

(*  Pascal  *)

(*----------------------

  VIEC.PAS Chon viec

-----------------------*)

program viec;

uses crt;

const

  MN = 200; bl = #32; {dau cach}

  nl = #13#10; {xuong dong}

  fn = 'viec.inp'; {input file}

  gn = 'viec.out'; {output file}

var

  a,id,t: array[1..MN] of integer;

  {a: tien thuong, t: thoi han giao nop}

  {id: chi dan}

  h: array[0..MN] of integer; {truc thoi gian}

  N: integer; {so luong viec}

  f,g: text;

  M: integer; {so viec da xep}

  tt: longint; {tong so tien thuong}

(*----------------------------

  Doc du lieu tu input file

------------------------------*)

procedure Doc;

var i,k: integer;

begin

assign(f,fn); reset(f);

readln(f,N);

for i := 1 to N do

readln(f,t[i],a[i]);

close(f);

end;

(*----------------------------

 Khoi tri cho mang chi dan id

------------------------------*)

procedure InitID;

var i: integer;

begin

for i :=  1 to N do id[i] :=  i;

end;

(*-----------------------------------

      Sap giam a[1..N] theo chi dan

--------------------------------------*)

procedure IDQuickSort(d,c: integer);

var i, j, m, k: integer;

begin

i :=  d; j :=  c;

m :=  a[id[(i+j) div 2]]; {phan tu giua}

while i <= j do

begin

  while a[id[i]] > m do inc(i);

   while a[id[j]] < m do dec(j);

   if i <= j then

    begin

  k :=  id[i];

  id[i] :=  id[j];

  id[j] :=  k;

  inc(i); dec(j);

    end;

end;

if d < j then IDQuickSort(d,j);

if i < c then IDQuickSort(i,c);

end;

(*-------------------------------------

Xep viec theo giai thuat tham lam

---------------------------------------*)

procedure XepViec;

var i,k,v: integer;

begin

fillchar(h,sizeof(h),0);

for i :=  1 to N do

begin

v :=  id[i]; {viec nao}

for k :=  t[v] downto 1 do

  if h[k]= 0 then

  begin

    {xep duoc viec v tai thoi diem k}

    h[k] :=  v;

    id[i] :=  -v;

    break;

  end;

end;

end;

(*------------------------------------

Don cac viec da xep trong h len phia truoc

va tinh tong tien thuong

-------------------------------------*)

procedure DonViec;

var i: integer;

begin

tt := 0;

{tim gio trong dau tien trong h}

for i := 1 to MN do

if h[i]=0 then

 begin

  M := i;

  break;

end

else tt := tt+a[h[i]];

if M > N then exit;

for i := M+1 to MN do

if h[i] > 0 then

begin

  h[M] := h[i];

  tt := tt+a[h[i]];

  inc(M);

  if M > N then exit;

end;

end;

(*---------------------------------------

            Xep not cac viec con lai

----------------------------------------*)

procedure XepTiep;

var i: integer;

begin

for i := 1 to N do

    if id[i] > 0 then

    begin

  h[M] := id[i];

  inc(M);

    end;

end;

(*-----------------------------

            Ghi ket qua

------------------------------*)

procedure GhiTep;

var i: integer;

begin

assign(g,gn); rewrite(g);

for i :=  1 to N do

writeln(g,h[i]);

writeln(g,tt); close(g);

end;

BEGIN

Doc; InitID; IDQuickSort(1,n);

XepViec; DonViec; XepTiep; GhiTep;

END.