回 帖 发 新 帖 刷新版面

主题:谁能帮下忙把下面的pascal转成C或C++,多谢了!

例1:设有5人从事5项工作每人只能从事一项,它们的
效益表如下:
     j1    j2    j3    j4    j5
A    13    11    10    4    7
B    13    10    10    8    5
C    5    9    7    7    4
D    15    12    10    11    5
E    10    11    8    8    4
求最佳安排,使效益最高?
  
program PlanJob;

const MAX_SIZE = 20;

type
  TIntArray = array[1..MAX_SIZE] of Integer;
  PNode = ^Node;
  Node = record
    Job2Man: TIntArray;    // Job2Man[n] = m, job-n assign to person-m
    Man2Job: TIntArray;    // Man2Job[n] = m, person-n assign to job-m
    UpperVal: Integer; // upper value
    JobsDep: Integer;   // jobs decided, as search depth
    Next: PNode;
  end;

var
   CurNode: PNode;      // Current node
   NewNode: PNode;      // New branch node
   DelNode: PNode;      // for delete
   GoalNode: PNode;     // the goal
   GoalMaxVal: Integer; // goal max value
   CurMan, CurJob: Integer;     // Current Man and Job of current Node

   Size: Integer;       // Person number, also task number
   Values: array[1..MAX_SIZE, 1..MAX_SIZE] of Integer;

function CalUpperValue(ANode: PNode): Integer;
var
  Res: Integer;
  Man, Job: Integer;
  JobMaxVal: Integer;
begin
  Res := 0;
  with ANode^ do
  begin
    for Job := 1 to Size do
    begin
      if Job <= JobsDep then
      begin
        Man := Job2Man[Job];
        Res := Res + Values[Man, Job];
        Continue;
      end;

      // else find the max value for Job
      JobMaxVal := 0;
      for Man := 1 to Size do
      begin
        if (JobMaxVal < Values[Man,Job]) and (Man2Job[Man] = 0) then
          JobMaxVal := Values[Man,Job];
      end;
      Res := Res + JobMaxVal;
    end;    // for Job
  end;    // with ANode^
  CalUpperValue := Res;
end;

function InitNode(): PNode;
var
  Man, Job: Integer;
  FInput: Text;
  Res: PNode;
begin
  Assign(FInput, 'input.txt');
  Reset(FInput);
  Read(FInput, Size);
  Readln(FInput);
  for Man := 1 to Size do
  begin
    for Job := 1 to Size do
      Read(FInput, Values[Man,Job]);
    Readln(FInput);
  end;

  New(Res);
  with Res^ do
  begin
    for Man := 1 to Size do
    begin
      Man2Job[Man] := 0;
      Job2Man[Man] := 0;
    end;
    JobsDep := 0;
    UpperVal := CalUpperValue(Res);
    Next := nil;
  end;
  InitNode := Res;
end;

procedure Insert(ANode: PNode; From: PNode);
var
  PrevNode, NextNode: PNode;
begin
  NextNode := From;
  repeat
    PrevNode := NextNode;
    NextNode := PrevNode^.Next;
  until (NextNode = nil) or (ANode^.UpperVal >= NextNode^.UpperVal);
  PrevNode^.Next := ANode;
  ANode^.Next := NextNode;
end;

procedure PrintNode(ANode: PNode);
var
  Man, Job: Integer;
  AllJobAssigned: Boolean;
begin
  AllJobAssigned := true;
  for Job := 1 to Size do
  begin
    Man := ANode^.Job2Man[Job];
    if 0 <> Man then
      Writeln('Job ', Job, ' assign to man ',
        Man, ', value ', Values[Man, Job])
    else
      AllJobAssigned := false;
  end;
  Writeln;
  if AllJobAssigned then
    Writeln('Value = ', ANode^.UpperVal)
  else
    Writeln('UpperVal = ', ANode^.UpperVal);
end;

begin
  CurNode := InitNode();
  GoalMaxVal := 0;

  repeat
    CurJob := CurNode^.JobsDep + 1;
    for CurMan := 1 to Size do
    begin
      if CurNode^.Man2Job[CurMan] <> 0 then
        Continue;

      // New search branch
      New(NewNode);
      NewNode^ := CurNode^;
      NewNode^.JobsDep := CurJob;
      NewNode^.Man2Job[CurMan] := CurJob;
      NewNode^.Job2Man[CurJob] := CurMan;
      NewNode^.UpperVal := CalUpperValue(NewNode);

      if NewNode^.UpperVal < GoalMaxVal then
        Dispose(NewNode)        // discard this branch if smaller than limit
      else
        Insert(NewNode, CurNode);

      if CurJob < Size then Continue;   // for CurMan

      // all job assigned, update goal
      if NewNode^.UpperVal > GoalMaxVal then
      begin
        GoalNode := NewNode;
        GoalMaxVal := GoalNode^.UpperVal
      end;  // if
    end;    // for CurMan

    DelNode := CurNode;
    CurNode := CurNode^.Next;
    Dispose(DelNode);
  until (CurNode^.UpperVal <= GoalMaxVal)
    or (CurNode = nil);    // end of repeat

  PrintNode(GoalNode);
  Readln;
end.
0

回复列表 (共4个回复)

沙发

天啊,简单的搜索程序怎么连指针都有……
与其修改程序还不如直接重写一个呢。

我Pascal不错,C++一塌糊涂,下面的大概其是这么回事。

#include <iostream.h>
const int g[5][5]=
  {{13,11,10, 4, 7},
   {13,10,10, 8, 5},
   { 5, 9, 7, 7, 4},
   {15,12,10,11, 5},
   {10,11, 8, 8, 4}};
void main(){
  int a,b,c,d,e;
  int sum,max=0,v,w,x,y,z;
  for (a=1;a<=5;a++)
   for (b=1;b<=5;b++) if (b!=a)
   for (c=1;c<=5;c++) if ((c!=a) && (c!=b))
   for (d=1;d<=5;d++) if ((d!=a) && (d!=b) && (d!=c))
   for (e=1;e<=5;e++) if ((e!=a) && (e!=b) && (e!=c) && (e!=d)) {
    sum=g[0][a-1]+g[1][b-1]+g[2][c-1]+g[3][d-1]+g[4][e-1];
    if (sum>max) {
      v=a;w=b;x=c;y=d;z=e;
      max=sum;
    }
  }
  cout<<max<<endl<<v<<" "<<w<<" "<<x<<" "<<y<<" "<<z<<endl;
}

板凳


先谢谢楼上的了。
之前忘了说了,题目要求是要用分支定界法的。

3 楼


2楼的,您忘写using namespace std;了

4 楼

[quote]
2楼的,您忘写using namespace std;了

[/quote]
Dev Cpp貌似不用写这个

我来回复

您尚未登录,请登录后再回复。点此登录或注册