Description

假設有n個任務由k個并行工作的機器來完成。完成任務i需要的時間為Ti。試設計一個算法找出完成這n個任務的最佳調度，使得完成全部任務的時間最早。
算法設計：對任意給定的整數n和k，以及完成任務i需要的時間為Ti，i=1，2，3……n。計算完成這n個任務的最佳調度。

Input

第一行有2個正整數n和k。第2行的n個正整數是完成n個任務需要的時間。

Output

將計算的完成全部任務的最早時間

Sample Input

7 3 2 14 4 16 6 5 3

Sample Output

17

這題我是用搜索來做的

這題有點像接水問題

var n,k,tj,i:longint; b,t:array[0..10000]of longint; procedure kp(l,r:longint); var i,j,mid:longint; beginif l>=r then exit;i:=l;j:=r;mid:=t[(l+r)div 2];repeatwhile t[i]>mid do inc(i);while t[j]<mid do dec(j);if i<=j thenbegint[0]:=t[i];t[i]:=t[j];t[j]:=t[0];inc(i);dec(j);end;until i>j;kp(l,j);kp(i,r); end; procedure search(dep,time:longint); var i:longint; beginif dep>n thenif time<tj thenbegintj:=time;exit;end;if time>=tj then exit;for i:=1 to k dobeginb[i]:=b[i]+t[dep];if b[i]>time then search(dep+1,b[i]) else search(dep+1,time);b[i]:=b[i]-t[dep];end; end; beginreadln(n,k);tj:=10000;fillchar(t,sizeof(t),0);for i:=1 to n doread(t[i]);kp(1,n);fillchar(b,sizeof(b),0);search(1,0);write(tj); end.

轉載于:https://www.cnblogs.com/YYC-0304/p/9500239.html

總結

以上是生活随笔為你收集整理的最佳调度问题pascal程序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。