六、 给定一个带期限的作业排序问题, n=5, (p1,p2,p3,p4,p5)=(6,3,4,8,5), (t1,t2,t3,t4,t5)=(2,1,2,1,1), (d1,d2,d3,d4,d5)= (3,1,4,2,4), 应用FIFOBB求使总罚款数最小的可行作业集J, 要求:
1）阐述c’(X)和u(X)的设计思路，U的初始值;
2）针对解向量变长格式, 画出FIFOBB的生成的部分状态空间树, 按活节点生成顺序给节点编号，在各节点位置给出c’(X)和U的值，给每条边标记选择的作业编号;
3）阐述c’(X)=U的处理方案, 可行解的判断方案；
4）阐述你程序中的主要数据类型、数据变量和功能模块。
5）、编成并上机实现FIFOBB程序, 实现对不同作业排序问题实例的求解，问题实例的输入数据存储在case.txt文件中，其格式为：
第一行 问题规模（最多10个作业）
第二行 各作业的罚款数，数据项之间用一个空格分隔
第三行 各作业的截止期限，数据项之间用一个空格分隔
第四行 各作业所需的运行时间，数据项之间用一个空格分隔
例如：
4
5 10 6 3
1 3 2 1
1 2 1 1
从屏幕直接输出最优作业集的序号，数据项之间用逗号分隔。
Program Tasks_with_limit_and_fine;
Const
Maxn = 500;
Type
Node = Record
k, d, w : Integer
End;
Var
N, i, j, num, t : Integer;
F : Text;
List, Lt : Array [1..Maxn] of Node;
Pck : Array [1..Maxn] of Integer;
Procedure Merge(p, q, r : Integer);
Var
i, j, t : Integer;
Begin
t := p; i := p; j := q + 1;
While t <= r Do Begin
If (i <= q) And ((j > r) Or (List[i].w > List[j].w)) Then
Begin
Lt[t] := List[i]; Inc(i)
End{then}
Else Begin
Lt[t] := List[j]; Inc(j)
End;{else}
Inc(t)
End;{while}
For i := p to r Do List[i] := Lt[i]
End;{Merge}
Procedure Merge_Sort(p, r : Integer);
Var
q : Integer;
Begin
If p <> r Then Begin
q := (p + r - 1) div 2;
Merge_Sort(p, q);
Merge_Sort(q + 1, r);
Merge(p, q ,r)
End{then}
End;{Merge_sort}
Begin
Assign(F, 'INPUT.DAT');
Reset(F);
Readln(F, N);
For i := 1 to N Do Begin
Readln(F, List[i].d, List[i].w);
List[i].k := i
End;{for}
Merge_Sort(1, N);
num := 0;
For i := 1 to N Do Begin
t := 0;
For j := 1 to num Do
If List[Pck[j]].d <= num Then Inc(t);
If t < List[i].d Then Begin
Inc(num);
Pck[num] := i;
List[i].k := - List[i].k;
j := num;
While (j > 1) And (List[Pck[j]].d < List[Pck[j - 1]].d)
Do Begin
t := Pck[j]; Pck[j] := Pck[j - 1]; Pck[j - 1] := t;
Dec(j)
End{while}
End{then}
End;{for}
For i := 1 to num Do Write(- List[Pck[i]].k:4);
t := 0;
For i := 1 to N Do
If List[i].k > 0 Then Begin
Write(List[i].k:4);
t := t + List[i].w
End;
Writeln;
Writeln('Total fine = ', t){????×?·?????}
End.{main}
Const
Maxn = 500;
Type
Node = Record
k, d, w : Integer
End;
Var
N, i, j, num, t : Integer;
F : Text;
List, Lt : Array [1..Maxn] of Node;
Pck : Array [1..Maxn] of Integer;
Procedure Merge(p, q, r : Integer);
Var
i, j, t : Integer;
Begin
t := p; i := p; j := q + 1;
While t <= r Do Begin
If (i <= q) And ((j > r) Or (List[i].w > List[j].w)) Then
Begin
Lt[t] := List[i]; Inc(i)
End{then}
Else Begin
Lt[t] := List[j]; Inc(j)
End;{else}
Inc(t)
End;{while}
For i := p to r Do List[i] := Lt[i]
End;{Merge}
Procedure Merge_Sort(p, r : Integer);
Var
q : Integer;
Begin
If p <> r Then Begin
q := (p + r - 1) div 2;
Merge_Sort(p, q);
Merge_Sort(q + 1, r);
Merge(p, q ,r)
End{then}
End;{Merge_sort}
Begin
Assign(F, 'INPUT.DAT');
Reset(F);
Readln(F, N);
For i := 1 to N Do Begin
Readln(F, List[i].d, List[i].w);
List[i].k := i
End;{for}
Merge_Sort(1, N);
num := 0;
For i := 1 to N Do Begin
t := 0;
For j := 1 to num Do
If List[Pck[j]].d <= num Then Inc(t);
If t < List[i].d Then Begin
Inc(num);
Pck[num] := i;
List[i].k := - List[i].k;
j := num;
While (j > 1) And (List[Pck[j]].d < List[Pck[j - 1]].d)
Do Begin
t := Pck[j]; Pck[j] := Pck[j - 1]; Pck[j - 1] := t;
Dec(j)
End{while}
End{then}
End;{for}
For i := 1 to num Do Write(- List[Pck[i]].k:4);
t := 0;
For i := 1 to N Do
If List[i].k > 0 Then Begin
Write(List[i].k:4);
t := t + List[i].w
End;
Writeln;
Writeln('Total fine = ', t){????×?·?????}
End.{main}
温馨提示：答案为网友推荐，仅供参考
