分支定界法的思想是首先确定目标值的上下界.docx
《分支定界法的思想是首先确定目标值的上下界.docx》由会员分享，可在线阅读，更多相关《分支定界法的思想是首先确定目标值的上下界.docx（10页珍藏版）》请在冰点文库上搜索。
分支定界法的思想是首先确定目标值的上下界
分支定界法的思想是：
首先确定目标值的上下界
发布人：
chengxu0921发布时间：
2008-7-2118:
16:
27新闻类别：
分支-界限法
例1：
设有A,B,C,D,E5人从事j1,j2,j3,j4,j55项工作每人只能从事一项,它们的
效益表如下:
j1j2j3j4j5
A
B131085
C59774
D5
E
求最佳安排,使效益最高？
原文代码重写如下，希望增加点可读性。
programPlanJob;
constMAX_SIZE=20;
type
TIntArray=array[
1..MAX_SIZE]ofInteger;
PNode=^Node;
Node=record
Job2Man:
TIntArray;//Job2Man[n]=m,job-nassigntoperson-mMan2Job:
TIntArray;//Man2Job[n]=m,person-nassigntojob-mUpperVal:
Integer;//uppervalue
JobsDep:
Integer;//jobsdecided,assearchdepth
Next:
PNode;
end;
var
CurNode:
PNode;//Currentnode
NewNode:
PNode;//Newbranchnode
DelNode:
PNode;//fordelete
GoalNode:
PNode;//thegoal
GoalMaxVal:
Integer;//goalmaxvalue
CurMan,CurJob:
Integer;//CurrentManandJobofcurrentNodeSize:
Integer;//Personnumber,alsotasknumber
Values:
array[
1..MAX_SIZE,
1..MAX_SIZE]ofInteger;
functionCalUpperValue（ANode:
PNode）:
Integer;
var
Res:
Integer;
Man,Job:
Integer;
JobMaxVal:
Integer;
begin
Res:
=0;
withANode^do
begin
forJob:
=1toSizedo
begin
ifJob<=JobsDepthen
begin
Man:
=Job2Man[Job];
Res:
=Res+Values[Man,Job];
Continue;
end;
//elsefindthemaxvalueforJob
JobMaxVal:
=0;
forMan:
=1toSizedo
begin
if（JobMaxVal=Values[Man,Job];
end;
Res:
=Res+JobMaxVal;
end;//forJob
end;//withANode^
CalUpperValue:
=Res;
end;
functionInitNode（）:
PNode;
var
Man,Job:
Integer;
FInput:
Text;
Res:
PNode;
begin
Assign（FInput,'input.txt'）;
Reset（FInput）;
Read（FInput,Size）;
Readln（FInput）;
forMan:
=1toSizedo
begin
forJob:
=1toSizedo
Read（FInput,Values[Man,Job]）;
Readln（FInput）;
end;
New（Res）;
withRes^do
begin
forMan:
=1toSizedo
begin
Man2Job[Man]:
=0;
Job2Man[Man]:
=0;
end;
JobsDep:
=0;
UpperVal:
=CalUpperValue（Res）;
Next:
=nil;
end;
InitNode:
=Res;
end;
procedureInsert（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;
procedurePrintNode（ANode:
PNode）;
var
Man,Job:
Integer;
AllJobAssigned:
Boolean;
begin
AllJobAssigned:
=true;
forJob:
=1toSizedo
begin
Man:
=ANode^.Job2Man[Job];
if0<>Manthen
Writeln（'Job',Job,'assigntoman',
Man,',value',Values[Man,Job]）
else
AllJobAssigned:
=false;
end;
Writeln;
ifAllJobAssignedthen
Writeln（'Value=',ANode^.UpperVal）
else
Writeln（'UpperVal=',ANode^.UpperVal）;
end;
begin
CurNode:
=InitNode（）;
GoalMaxVal:
=0;
repeat
CurJob:
=CurNode^.JobsDep+1;
forCurMan:
=1toSizedo
begin
ifCurNode^.Man2Job[CurMan]<>0then
Continue;
//Newsearchbranch
New（NewNode）;
NewNode^:
=CurNode^;
NewNode^.JobsDep:
=CurJob;
NewNode^.Man2Job[CurMan]:
=CurJob;
NewNode^.Job2Man[CurJob]:
=CurMan;
NewNode^.UpperVal:
=CalUpperValue（NewNode）;
ifNewNode^.UpperValDispose（NewNode）//discardthisbranchifsmallerthanlimitelse
Insert（NewNode,CurNode）;
ifCurJob//alljobassigned,updategoal
ifNewNode^.UpperVal>GoalMaxValthen
begin
GoalNode:
=NewNode;
GoalMaxVal:
=GoalNode^.UpperVal
end;//if
end;//forCurMan
DelNode:
=CurNode;
CurNode:
=CurNode^.Next;
Dispose（DelNode）;
until（CurNode^.UpperVal<=GoalMaxVal）
or（CurNode=nil）;//endofrepeat
PrintNode（GoalNode）;
Readln;
end.
input.txt:
7
131085
59774
5
output:
Job1assigntoman4,value15
Job2assigntoman5,value11
Job3assigntoman2,value10
Job4assigntoman3,value7
Job5assigntoman1,value7
Value=50
如果扩展为10*10,
input.txt:
10
59774
5
59774
5
运行约两分钟。
output:
Job1assigntoman9,value15
Job2assigntoman5,value11
Job3assigntoman2,value10
Job4assigntoman8,value7
Job5assigntoman6,value7
Job6assigntoman4,value15
Job7assigntoman10,value11
Job8assigntoman7,value10
Job9assigntoman3,value7
Job10assigntoman1,value7
Value=100
升级会员 