PRO_4_1.pas 3.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129
  1. Program Pro_4_1; {例4的动态规划算法}
  2. Const
  3. Map:Array['A'..'G','A'..'G'] Of Byte= {每两个农场之间的距离}
  4. ((0,56,43,71,35,41,36),
  5. (56,0,54,58,36,79,31),
  6. (43,54,0,30,20,31,58),
  7. (71,58,30,0,38,59,75),
  8. (35,36,20,38,0,44,67),
  9. (41,79,31,59,44,0,72),
  10. (36,31,58,75,67,72,0));
  11. Inputfile ='Input.Txt'; {输入文件名}
  12. Outputfile ='Output.Txt'; {输出文件名}
  13. Type
  14. Kus =Array[0..4095] Of Word; {权值数组类型说明}
  15. Dirs =Array[0..4095] Of Byte; {标记数组类型说明}
  16. Ses =Set Of 1..12; {集合类型}
  17. Var
  18. F :Text; {文件变量}
  19. N :Integer; {任务数目}
  20. Wu :Array[0..12,1..2] Of Char; {记录任务的数组}
  21. Dis :Array[0..12,0..12] Of Integer; {每两个任务的连接费用}
  22. Ku :Array[1..12] Of ^kus; {动态规划中记录权值的数组}
  23. Dir :Array[1..12] Of ^dirs; {动态规划的标记数组}
  24. Procedure Init; {初始化过程}
  25. Var
  26. I :Integer;
  27. Ch :Char;
  28. Begin
  29. Assign(F,Inputfile);
  30. Reset(F);
  31. Readln(F,N);
  32. For I:=1 To N Do {读入数据}
  33. Readln(F,Wu[I,1],Ch,Wu[I,2]);
  34. Close(F);
  35. End;
  36. Procedure Prepare; {准备过程}
  37. Var
  38. I,J :Integer;
  39. Begin
  40. Wu[0,1]:='A';Wu[0,2]:='A'; {求出每两个任务的连接费用}
  41. For I:=0 To N Do
  42. For J:=0 To N Do
  43. Dis[I,J]:=Map[Wu[I,2],Wu[J,1]];
  44. End;
  45. Procedure Main; {动态规划过程}
  46. Var
  47. Last,I,K,What :Word;
  48. S :Ses;
  49. Function Num(S:Ses):Word; {将集合转化为整数的函数}
  50. Var
  51. X :Word Absolute S;
  52. Begin
  53. Num:=X Div 2;
  54. End;
  55. Procedure Did(Dep,From:Byte;S:Ses); {为动态规划中记录权值的数组赋值}
  56. Var
  57. I :Byte;
  58. Begin
  59. If Dep>K Then
  60. Begin
  61. For I:=1 To N Do
  62. If (I In S) And (Ku[I]^[Num(S-[I])]+Dis[What,I]<Ku[What]^[Num(S)]) Then
  63. Begin {如果更小,改变现有权值与表示变量}
  64. Ku[What]^[Num(S)]:=Ku[I]^[Num(S-[I])]+Dis[What,I];
  65. Dir[What]^[Num(S)]:=I;
  66. End;
  67. End
  68. Else
  69. For I:=From+1 To N Do
  70. If I<>What Then
  71. Did(Dep+1,I,S+[I]);
  72. End;
  73. Begin
  74. For I:=1 To N Do {初始化动态规划记录数组}
  75. Begin
  76. New(Ku[I]);
  77. New(Dir[I]);
  78. Fillchar(Ku[I]^,Sizeof(Ku[I]^),$ff);
  79. End;
  80. For I:=1 To N Do
  81. Ku[I]^[0]:=Dis[I,0];
  82. For K:=1 To N-1 Do {为动态规划数组赋值}
  83. For What:=1 To N Do
  84. Did(1,0,[]);
  85. S:=[1..N];
  86. K:=60000;
  87. For I:=1 To N Do
  88. If Dis[0,I]+Ku[I]^[Num(S-[I])]<K Then
  89. Begin
  90. K:=Dis[0,I]+Ku[I]^[Num(S-[I])];
  91. What:=I;
  92. End;
  93. For I:=1 To N Do
  94. Inc(K,Map[Wu[I,1],Wu[I,2]]);
  95. Assign(F,Outputfile); {输出结果}
  96. Rewrite(F);
  97. Writeln(F,K);
  98. Write(F,'A ');
  99. Last:=0;
  100. For I:=1 To N Do
  101. Begin
  102. If Wu[Last,2]<>Wu[What,1] Then Write(F,Wu[What,1],' ');
  103. Write(F,Wu[What,2],' ');
  104. Exclude(S,What);
  105. Last:=What;
  106. What:=Dir[What]^[Num(S)];
  107. End;
  108. If 'A'<>Wu[Last,2] Then Write(F,'A');
  109. Close(F);
  110. End;
  111. Begin
  112. Init; {初始化}
  113. Prepare; {准备}
  114. Main; {计算}
  115. End.