求解一最优分割算法,是不是太多的开发工具让大家不再专注于算法研究了...... (300分)

使用整数线性规划故然可以,但是不是有点杀鸡用牛刀的感觉呢?其实用宽度搜索足矣
interface
uses
SysUtils, Classes, Dialogs;
const
n = 2;
//材料总数
Len = 60;
//料坯长度
MatLen: array [1..n] of Integer = (55, 5);
//各种材料长度(按大到小)
MatQty: array [1..n] of Integer = (12, 12);
//各种材料需要的数量
type
//定义节点记录
PNode = ^TNode;
TNode = record
Count: Integer;
//节点所在层,等于所用料坯数量
MatCnt: array [1..n] of Integer;
//到当前节点为至,各种材料的数量
PrjIndex: Integer;
//当前节点使用的开料方案
Parent: PNode;
//当前节点的父节点
end;

//节点队列,用于宽度搜索
TNodeList = class(TList)
private
function GetItem(Index: Integer): PNode;
protected
procedure Notify(Ptr: Pointer;
Action: TListNotification);
override;
public
property Items[Index: Integer]: PNode read GetItem;
default;
end;

var
MatPrj: array of array [1..n] of Integer;
//记录各开料方案
MatPrjCnt: Integer;
//开料方案数

procedure CalcProject;
procedure OptimalProject;
implementation
//计算开料方案
procedure CalcProject;
var
Prj: array [1..n] of Integer;
procedure CalcProjectSub(Len, Index: Integer);
//Len当前剩余料坯长度,用剩余料坯开第Index总材料
var
RemLen, Max, i: Integer;
begin
//递归退出条件
if (Len = 0) or (Index > n) then
begin
Inc(MatPrjCnt);
SetLength(MatPrj, MatPrjCnt);
Move(Prj[1], MatPrj[MatPrjCnt - 1][1], SizeOf(Prj));
Exit;
end;

//计算剩余料坯长度可以最多开多少第Index种材料
Max := Len div MatLen[Index];
if Index < n then
//当前不是开最后一种材料,则分别开0至Max个,保留部分料坯长度给后继材料
for i := Maxdo
wnto 0do
begin
Prj[Index] := i;
RemLen := Len - i * MatLen[Index];
//料坯长度为0,其后的材料不能再开,所以设0
if RemLen = 0 then
FillChar(Prj[Index + 1], (n - Index) * SizeOf(Integer), 0);
CalcProjectSub(RemLen, Index + 1);
end
else
begin
//最后一种材料了,设置最大的开料数量即可
Prj[Index] := Max;
CalcProjectSub(0, Index + 1);
end;
end;

begin
//初始开料方案
SetLength(MatPrj, 0);
MatPrjCnt := 0;
//由于材料的数量n不定,故用递归方案计算各开料方案
CalcProjectSub(Len, 1);
end;

function CheckSuccess(Node: PNode): Boolean;
//检查当前的方案是否已经满足MatQty的要求
var
i: Integer;
begin
Result := True;
for i := 1 to ndo
if Node.MatCnt < MatQty then
begin
//只要其中一个小于MatQty,则为不满足
Result := False;
Break;
end;
end;

procedure ShowSolution(Node: PNode);
//显示第一个解决方案
var
s: String;
i: Integer;
begin
s := Format('所需要的最少料坯数量: %d'#13#10'开料方案如下:'#13#10,
[Node.Count]);
while Assigned(Node)do
begin
for i := 1 to ndo
AppendStr(s, IntToStr(MatPrj[Node.PrjIndex, i]) + ' ');
AppendStr(s, #13#10);
Node := Node.Parent;
end;

ShowMessage(s);
end;

procedure OptimalProject;
//求解最优方案
var
List: TNodeList;
Node, NewNode: PNode;
i, j, p: Integer;
begin
//建立队列
List := TNodeList.Create;
try
//初始化队列中的元素,即把各种方案入队
for i := 0 to MatPrjCnt - 1do
begin
New(Node);
with Node^do
begin
Count := 1;
Move(MatPrj[1], MatCnt[1], SizeOf(MatCnt));
PrjIndex := i;
Parent := nil;
end;

List.Add(Node);
//检查是否某一种开料方案即可满足要求
if CheckSuccess(Node) then
begin
ShowSolution(Node);
Exit;
end;
end;

p := 0;
while p < List.Countdo
begin
//从列队中取出第一个节点
Node := List[p];
//在第一个节点基础上,在分别开一条料坯并入队列
for i := Node.PrjIndex to MatPrjCnt - 1do
begin
New(NewNode);
with NewNode^do
begin
Count := Node.Count + 1;
Move(Node.MatCnt[1], MatCnt[1], SizeOf(MatCnt));
for j := 1 to ndo
Inc(MatCnt[j], MatPrj[i, j]);
PrjIndex := i;
Parent := Node;
end;

List.Add(NewNode);
//检测是否开了这一条料坯后,可以达到要求
if CheckSuccess(NewNode) then
begin
ShowSolution(NewNode);
Exit;
end;
end;

Inc(p);
end;
finally
List.Free;
end;
end;

{ TNodeList }
function TNodeList.GetItem(Index: Integer): PNode;
begin
Result := inherited Items[Index];
end;

procedure TNodeList.Notify(Ptr: Pointer;
Action: TListNotification);
begin
if Action = lnDeleted then
Dispose(PNode(Ptr));
inherited;
end;

调用方法
begin
CalcProject;
OptimalProject;
end;

如果要考虑料头或者料间,或者需要多种解决方案,适当修改即可.

up

设要求加工的钢管长度、数量放在链表中（并按长度排序）
节点为 长度l+数量n+一个指针（指向下一节点）。p为头节点
q为另一链表，存放加工顺序；q->next=nil;q1=q;
程序如下
L0 = 0;
while (p<>nil)do
begin
if(p->n = 0) p= p->next
else
begin
L0=L;p0=p end;
//L为材料长度
while(L0 <> 0)do
begin
m = L0/p0->l;//(取下界，函数忘了）
if (m<=n)
[ L0= L0-m*p0->l;new(r);r->l=p0->l;r->n = m;
r->next = q->next;q->next = r;q=r;]
else
[ L0= L0-m*p0->l;new(r);r->l=p0->l;r->n = p0->n;
r->next = q->next;q->next = r;q=r;]
p0=p0->next;
if (p0=nil) L0=0； //此时可能有废料，可以加入判断有无废料的代码
end;
end;
q=q1->next;L1=n1=0;
//下面输出组合,
while (q1<>nil)do
begin
write(inttostr(q1->l)+"*"+inttostr(ql->n);//函数记不得了,可能不对：）
L1= L1+q1->l*q1->n;
if (L1 = L)[ writeln("="+ inttostr(L))+" ";L1 = 0;n1=n1+1;]
if (L1 > L) [writeln("<"+ inttostr(L);
L1=0;n1=n1+1;]
q1 = q1->next;
end;
if (L1 < L)[writeln("<"+ inttostr(L);
L1=0;n1=n1+1;]
writeln("共需要原料"+inttostr(n1)+"根")

一个医院为改进其服务，要求设计一个模拟程序来评估可选择的手术室、恢复室的配置方案。目前医院有5间手术室，12个恢复床位，医院从早晨7点开始可以进行手术，每个手术病人被分配到一个可用的手术室，手术之后病人被分配到恢复室的一个床位。将一个病人从手术室移至恢复室需要5分钟，为下一个病人准备手术室需要15分钟，为一个新病人准备一个恢复室需要10分钟。
假设某天有16个病人需要手术，每个人的手术时间和恢复时间如下：
病人姓名 手术时间（分） 恢复时间（分）
病人1 28 140
病人2 120 200
病人3 23 75
病人4 19 82
病人5 133 209
病人6 74 101
病人7 93 188
病人8 111 223
病人9 69 122
病人10 42 79
病人11 22 71
病人12 38 140
病人13 26 121
病人14 120 248
病人15 86 181
病人16 92 140
现需要编程输入以上所有的数据（包括手术室间数等），并列表输出手术室使用情况（包括编号、病人姓名、进入的手术室号、手术开始时间和手术结束时间）、恢复室使用情况（包括编号、病人姓名、进入的恢复室床号、进入时间和离开时间），并统计输出每间手术室和每张恢复床位的利用率（包括手术室号或恢复室床号，使用分钟数，利用率）。
要求：1、写出书面算法思想描述和算法结构描述。
2、输入数据存放在数据文件中，格式自定，在屏幕上以表格形式输出结果。

我要好好的看一看你的问题。

我的研究方向就是优化算法，主要是智能优化。现在从事的工作也跟这个有关。哪位兄弟有心，可以互相探讨。wangtao@cltc.com.cn

谢谢各位