oi ---pascal

来源：百度知道 编辑：UC知道 时间：2024/05/22 15:58:32
n个部件,每个部件必须经过先A后B两道工序。

以知部件i在A,B 机器上的时间分别为ai，bi。如何安排加工顺序，总加工时间最短？

具体解释做法
各位帮忙

先按bi/ai从大到小排列部件，再进行回溯搜索，搜索过程中尽量去除无用分支。

program gongxu;

{$APPTYPE CONSOLE}

uses
SysUtils,Math;

const
max_n = 100;

type
TPart = record
a,b:integer;
w:real;
used:boolean;
end;
TOrder = array[1..max_n] of integer;

var
parts:array[1..max_n] of TPart;
order:TOrder;
min_order:TOrder;
i,n,total_a,total_b,min_value,count:integer;
infile,outfile:text;

procedure sort(l,r:integer);
var
i,j,m:integer;
w0:real;
t:TPart;
begin
if (l > r)
then
exit;
i := l;
j := r;
m := (l+r) div 2;
w0 := parts[m].w;
t := parts[m];
parts[m] := parts[l];
parts[l] := t;
inc(i);
while (i <= j)
do
begin
while (i <= j) and (parts[i].w >= w0)
do
inc(i);
while (i <= j) a