请教算法:矩形体分解问题(300分)

  • 主题发起人 主题发起人 formater
  • 开始时间 开始时间
F

formater

Unregistered / Unconfirmed
GUEST, unregistred user!
把一个大的矩形体T0(长宽高x0,y0,z0)分解为n个小矩形体T1(长宽高x1,y1,z1),要求
n值最大时的分解方法。
 
n值最大没有解
 
真的没有解?难怪请教了一个高程一个系统分析员都不会做:(
 
我是高程,给你一个思路,看看能不能成,大致如下
1.将矩形的长宽高看成是一个袋子,大小分别是X,Y,Z三个袋子
2.将小矩形看成是石头,大小分别是A,B,C
3.首先我们装第一个袋子,比如是X,从A,B,C中找出可以使X最大充满时的A,B,C值,即Xmax(uA+vB+wC)时u,v,w的值,求这个的算法在数据结构的书中随处可见
4.求出上述值后,此时原来的大矩形可能被分解成了几个次大小的矩形(或者说是袋子),记录此时各个袋子的大小,以及可用的长宽高,比如说,对于将mA的这部分,此时,可以装的石头只有B与C了,对于vB的这部分,可装的只有A,C了,求出此时袋子可装的最大石头数,如Y(A)max=eB+fC
5.类似的可以求出Z(A,B)=gC
6.将各个袋子可装的小矩形数累加即可得到总的装箱数
算法中可将求Xmax(uA+vB+wC),Y(A)max=eB+fC做成一个函数, 可将袋子装石头的数量也做成函数,主调函数主要记录各个袋子的剩余可用的尺寸情况即可.
以上只是一个算法的思路,具体的实现可以都看看数据结构的书,以及一个叫火狐装箱程序(网上有下载,不过没有算法哦,而且装的也不仅仅是一个尺寸的石头,比你这个要复杂的多),
 
多谢!但是你这个算法好像适合平面的分解,这个是立体的……
 
这问题看来没有满意答案了
谁给个delphi源码 的二叉树建立、插入、删除的例子即给分。
 
请问我自己写的这个二叉树,为什么总是堆栈溢出的错误?
unit d1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TCutMode = (
ZX,
ZY,
ZZ,
YX,
YY,
YZ,
XX,
XY,
XZ,
NO
);
// 切割方法:ZX表示,保持X轴Y轴不变,沿着Z轴切割,厚度为小矩形体的X值
// NO表示没法继续切割
type
TNodeData = record // 节点的属性:
X, Y, Z: integer;
// 目前矩形体的长、宽、高
IsResult: boolean;
// 是否为目标小矩形体
Mode: TCutMode;
// 目前矩形体切割模式
end;
TtdChildType = ({子节点类型}
ctLeft, {表示左子节点}
ctRight);
{表示右子节点}
PtdBinTreeNode = ^TtdBinTreeNode;
{二叉树节点指针}
TtdBinTreeNode = record //二叉树节点
//btParent : PtdBinTreeNode;
//父节点
btChild: array[TtdChildType] of PtdBinTreeNode;
//两个子节点
btData: TNodeData;
//节点的值
end;

type
TForm1 = class(TForm)
Edit1: TEdit;
Memo1: TMemo;
Button1: TButton;
procedure Button2Click(Sender: TObject);
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;
implementation
{$R *.dfm}
function GetN(node0: PtdBinTreeNode): integer;
//求二叉树中的小矩形体个数
var
count: integer;
begin
count := 0;
if node0 <> nil then
begin
if node0^.btData.IsResult then
begin
//目标小矩形
count := count + 1;
end;
if node0.btChild[ctleft] <> nil then
count := count + getn(node0.btchild[ctleft]);
if node0.btChild[ctright] <> nil then
count := count + getn(node0.btchild[ctright]);
end;
result := count;
end;

procedure DelNode(node0: PtdBinTreeNode);
//后序遍历,删除节点,释放内存
begin
if node0.btChild[ctleft] <> nil then
begin
DelNode(node0.btChild[ctleft]);
node0.btChild[ctleft]:=nil;
end;
if node0.btChild[ctright] <> nil then
begin
DelNode(node0.btChild[ctright]);
node0.btChild[ctright]:=nil;
end;
if node0 <> nil then
dispose(node0);
end;

function MaxN(x0, y0, z0, x1, y1, z1: integer): PtdBinTreeNode;
var
nd0p: array[0..9] of PtdBinTreeNode;
i, count, rcount, tcount: integer;
begin

count := 0;
rcount := 0;
for i := 0 to 0do
begin
form1.memo1.lines.add(inttostr(i));
showmessage(inttostr(i));
new(nd0p);
//分配内存
with nd0p.btDatado
begin
//当前矩形体赋初值
x := x0;
y := y0;
z := z0;
if (x0 = x1) and (y0 = y1) and (z0 = z1) then
isresult := true
else
isresult := false;
mode := no;
end;
nd0p.btChild[ctleft] := nil;
nd0p.btChild[ctright] := nil;
if z0 > z1 then
begin
nd0p.btData.Mode := zz;
//沿着Z轴以厚度Z1切割
nd0p.btChild[ctleft] := maxn(x0, y0, z1, x1, y1, z1);
nd0p.btChild[ctright] := maxn(x0, y0, z0 - z1, x1, y1, z1);
end;
tcount := getn(nd0p);//当前二叉树中目标小矩形体个数
if tcount > count then
//当前二叉树为更好的解
begin
count := tcount;
rcount := i;
if i > 0 then
begin
DelNode(nd0p[i - 1]);
//删除节点,释放内存
end;
end
else
begin
DelNode(nd0p);
end;

end;

result := nd0p[rcount];//返回最优解的二叉树
end;

procedure TForm1.Button1Click(Sender: TObject);
var
a: integer;
begin
a := getn(maxn(45, 34, 23, 45, 34, 11));
edit1.Text := inttostr(a);
end;
end.

请问我自己写的这个二叉树,为什么总是堆栈溢出的错误?
 
后退
顶部