高分求一算法，各位富翁特别是数学高手，帮忙解决.... (200分)

看来LeeChange兄，我是盯定你了...

我在《运筹学》里见过这样的算法，绿色封面的书。
你可以去书店找一下。

smiler_mei,我现在就有一本，翻了好一会，
可不知在哪里，你确定这本书里面有吗？
如果确定我就一页一页的找一下...

我有一个想法，不过太麻烦了：
例如有四个材料 b1,b2,b3,b4
先 按照每一个与标准材料匹配，找出最省的4个
然后 [b1b2,b3b4]，[b1b3,b2b4].... 两两一组，找出最省的两组
然后 是三个一组
然后 是四个一组
然后再总的找出最省的一组

这样列举运算时间太长，而且得不到答案，
如b1b2加起来后就没有这种规格的材料，这趟不就是白跑了吗？
我的想法有点象ReallyFail的，不过我也不知道这是不是最优的....

答案一定会有，就是太费时间了。

to yanyandt2:
不要到处造我的谣,我很厉害吗?我自己觉得我的脾气很好嘛.
to 洛吉:
你不要盯定我,这么长时间的沉默说明我碰到了困难.
这题其实是很经典的题目,不过原题中原料的长度只有一个.
确实要考虑效率问题.我刚才的想法的复杂度大约是P40,就算
有好的启发函数也几乎不能接受.如果你有耐心等的话,我想应
该能找到更好一点的办法.
另外,不知道你能不能接受较优解?
to yanyandt2:
可不可以提些建议.我已经打算放弃搜索.

其实我的问题里面还有如果每次截剩的材料不可用，
那么最优的解决方案也不能取，而要取倒数第二优的，
不过这也不是难题了，关键问题还是如题，
如果你有较优的解决方案，不妨给我参考参考。
e_mail:ultrainfo@vip.sina.com或
flamboyancel@sina.com

看看吧，因为公司不允许带硬盘或软盘进来的，而且你要的比我所做的复杂了很多。
你的是要把材料分成多种，难度大了很多！不过我那个速度上还可以！

to 洛吉:
"标准材料的规模对复杂度的影响很小很小。O(log以2为底的n)"
我刚才说的这句话是不对的,如果标准材料的尺寸只有一个,我已经有解了.但现在标准材料
有很多种,就需要在每一种需要的材料的排列上在求一次解.
我觉得这题可以拿图论中的网络流来做,呵呵,回去翻翻箱子,看看有没有什么可以借鉴的.

LeeChange,我指的“厉害”是skill厉害，不是脾气厉害 ^_^!!
凭我的能力还想不出更好的，不过可以慢慢想。
跟踪此贴，向你学习-_-

多谢各位富翁关心！！

to ：LeeChange
如果只有一种标准材料，那真的好办了，可现在是多种材料，
而且我还把问题简化来提出了...

呵呵，我相信你已经简化了,我看过的原题还要考虑每次切割的损耗.
不过那题可以用分支定界,这题就不太合适了.

这是机械优化设计中的典型例题，找找书吧，有很多方法

to ：蒋劲刚
我找了好多关于机械优化设计的书堆在旁边，就是找不到类似于这方面的材料，
您能给我介绍一本吗？

hehe,确实是经典的题目,很多书上都有.
而且我敢肯定我曾经看过此题及题解,只是现在真是老了,呵呵.
可以请creation-zy以及huntaway wrench YB_unique过来看看.

这个问题在机械优化设计中应该是一个最简单的问题....

可以参考人工智能和专家系统中的算法

都很牛啊[]

老兄，我的这个是纸箱生产企业的选料程序，代码我不知道往那里发，就贴上来了，有时间
的话可以参考一下，不过可能帮助不是很大！这是我选料分析单元。看不懂的话你再问我
好了!
unit AsSayFrm;
interface
uses SysUtils,Dialogs;
type
TSpecs=record
SpecsId:integer;
StockLong,StockWidth:integer;
StockCount,AllUsesCount,ReallyUsesCount:integer;
UsesThisWidthFlag:boolean;
SquanderScaleouble;
end;
TAcceptResult=record
Long,Width,Counts:integer;
QiPaoLong:double;
end;
TAcceptSpecs=record
AllAcceptResult:array of TAcceptResult;
IfAccept:boolean;
Areas:double;
LongUnitCount:integer;
end;
procedure AssayMaterial(const AWaBie,AMaterial:string;ALong,AWidth,AHeight:double;
ProduceCount:integer;ARepeatFlag:boolean;var AllAcceptSpecs:TAcceptSpecs);
procedure InitVars();
implementation
uses DmFrm, FunUnit;
var
MinSpecsWidth:integer=850;
MaxSpecsWidth:integer=1600;
SingleMaxLong:integer=2300;
do
ubleMaxLong:integer=2380;
MaxSquander:double=0.05;
AllSpecs:array of TSpecs;
procedure GetUseLongWidth(AWaBie,AMaterial:string;ALong,AWidth,AHeight:integer;
ARepeatFlag:boolean;var SpecsLong,SpecsWidth,LongUsesCount:integer);
begin
LongUsesCount:=1;
if AWaBie='1' then
begin
SpecsLong:=(ALong+AWidth)*2+30;
if (SpecsLong>SingleMaxLong) and (SpecsLong<=2*SingleMaxLong) then
begin
SpecsLong:=ALong+AWidth+30;
LongUsesCount:=2;
end;
if SpecsLong>2*SingleMaxLong then
begin
SpecsLong:=ALong+AWidth+30;
LongUsesCount:=4;
end;
end;
if AWaBie='2' then
begin
SpecsLong:=(ALong+AWidth)*2+40;
if (SpecsLong>DoubleMaxLong) and (SpecsLong<=2*DoubleMaxLong) then
begin
SpecsLong:=(ALong+AWidth)+40;
LongUsesCount:=2;
end;
if SpecsLong>2*DoubleMaxLong then
begin
SpecsLong:=ALong+AWidth+40;
LongUsesCount:=4;
end;
end;
if (SpecsLong mod 10)<>0 then
SpecsLong:=SpecsLong+10-(SpecsLong mod 10);
SpecsWidth:=AWidth+AHeight+10;
if ARepeatFlag then
SpecsWidth:=2*AWidth+AHeight+10;
end;
function GetBestWidth(AWidth:integer;var Multiple:integer):integer;
var
i1,i2,icounts,TmpSquander1,TmpSquander2,TmpWidth:integer;
begin
icounts:=MaxSpecsWidth div AWidth;
TmpSquander1:=AWidth;
for i1:=1 to icountsdo
begin
for i2:=(MinSpecsWidth div 50) to (MaxSpecsWidth div 50)do
begin
TmpSquander2:=(50*i2)-AWidth*i1;
if (TmpSquander2<TmpSquander1) and (TmpSquander2>=0) then
begin
TmpSquander1:=TmpSquander2;
Result:=(50*i2);
Multiple:=i1;
end;
end;
end;
end;
procedure ReadAllMaterial(AWaBie,AMaterial:string;ALong,AWidth:integer);
var i1:integer;
begin
with DmForm.QryPub1do
begin
Close;
Sql.Clear;
Sql.Add('select 规格代号,库存数量,长度,宽度 from 视图库存');
Sql.Add('where 瓦别代号='+AWaBie);
Sql.Add('and 原料代号='+AMaterial);
Sql.Add('and 长度>='+inttostr(ALong div 10));
Sql.Add('and 宽度>='+inttostr(AWidth div 10));
Open;
SetLength(AllSpecs,RecordCount+1);
i1:=1;
while not Eofdo
begin
AllSpecs[i1].SpecsId:=FieldByName('规格代号').AsInteger;
AllSpecs[i1].StockCount:=FieldByName('库存数量').AsInteger;
AllSpecs[i1].StockWidth:=FieldByName('宽度').AsInteger;
AllSpecs[i1].StockLong:=FieldByName('长度').AsInteger;
Next;
Inc(i1);
end;
end;
end;
procedure SortMaterial();
var i1,j1:integer;
begin
for i1:=2 to high(AllSpecs)do
begin
AllSpecs[0].SpecsId:=AllSpecs[i1].SpecsId;
AllSpecs[0].StockLong:=AllSpecs[i1].StockLong;
AllSpecs[0].StockWidth:=AllSpecs[i1].StockWidth;
AllSpecs[0].StockCount:=AllSpecs[i1].StockCount;
AllSpecs[0].AllUsesCount:=AllSpecs[i1].AllUsesCount;
AllSpecs[0].SquanderScale:=AllSpecs[i1].SquanderScale;
j1:=i1-1;
while AllSpecs[0].SquanderScale<AllSpecs[j1].SquanderScaledo
begin
AllSpecs[j1+1].SpecsId:=AllSpecs[j1].SpecsId;
AllSpecs[j1+1].StockLong:=AllSpecs[j1].StockLong;
AllSpecs[j1+1].StockWidth:=AllSpecs[j1].StockWidth;
AllSpecs[j1+1].StockCount:=AllSpecs[j1].StockCount;
AllSpecs[j1+1].AllUsesCount:=AllSpecs[j1].AllUsesCount;
AllSpecs[j1+1].SquanderScale:=AllSpecs[j1].SquanderScale;
dec(j1);
end;
AllSpecs[j1+1].SpecsId:=AllSpecs[0].SpecsId;
AllSpecs[j1+1].StockLong:=AllSpecs[0].StockLong;
AllSpecs[j1+1].StockWidth:=AllSpecs[0].StockWidth;
AllSpecs[j1+1].StockCount:=AllSpecs[0].StockCount;
AllSpecs[j1+1].AllUsesCount:=AllSpecs[0].AllUsesCount;
AllSpecs[j1+1].SquanderScale:=AllSpecs[0].SquanderScale;
end;
end;
function SetUsesEd(AAllUsesCount:integer;var AllAcceptSpecs:TAcceptSpecs):boolean;
var
i1,ProduceCount:integer;
begin
result:=False;
SetLength(AllAcceptSpecs.AllAcceptResult,0);
ProduceCount:=AAllUsesCount;
if Length(AllSpecs)=1 then
Exit;
for i1:=1 to high(AllSpecs)do
begin
if AllSpecs[i1].SquanderScale<=MaxSquander then
begin
if AllSpecs[i1].StockCount>=ProduceCount then
begin
AllSpecs[i1].ReallyUsesCount:=ProduceCount;
SetLength(AllAcceptSpecs.AllAcceptResult,length(AllAcceptSpecs.AllAcceptResult)+1);
AllAcceptSpecs.AllAcceptResult[High(AllAcceptSpecs.AllAcceptResult)].Long:=AllSpecs[i1].StockLong;
AllAcceptSpecs.AllAcceptResult[High(AllAcceptSpecs.AllAcceptResult)].Width:=AllSpecs[i1].StockWidth;
AllAcceptSpecs.AllAcceptResult[High(AllAcceptSpecs.AllAcceptResult)].Counts:=AllSpecs[i1].ReallyUsesCount;
AllAcceptSpecs.IfAccept:=False;
Result:=True;
Exit;
end
else
begin
ProduceCount:=ProduceCount-AllSpecs[i1].StockCount;
AllSpecs[i1].ReallyUsesCount:=AllSpecs[i1].StockCount;
SetLength(AllAcceptSpecs.AllAcceptResult,length(AllAcceptSpecs.AllAcceptResult)+1);
AllAcceptSpecs.AllAcceptResult[High(AllAcceptSpecs.AllAcceptResult)].Long:=AllSpecs[i1].StockLong;
AllAcceptSpecs.AllAcceptResult[High(AllAcceptSpecs.AllAcceptResult)].Width:=AllSpecs[i1].StockWidth;
AllAcceptSpecs.AllAcceptResult[High(AllAcceptSpecs.AllAcceptResult)].Counts:=AllSpecs[i1].ReallyUsesCount;
AllAcceptSpecs.IfAccept:=False;
end;
end
else
begin
Break;
end;
end;
end;
procedure InitVars();
begin
with DmForm.QryPub1do
begin
Close;
Sql.Clear;
Sql.Add('select * from AsSayConst');
Open;
if not IsEmpty then
begin
MinSpecsWidth:=FieldByName('MinSpecsWidth').AsInteger;
MaxSpecsWidth:=FieldByName('MaxSpecsWidth').AsInteger;
SingleMaxLong:=FieldByName('SingleMaxLong').AsInteger;
do
ubleMaxLong:=FieldByName('DoubleMaxLong').AsInteger;
MaxSquander:=FieldByName('MaxSquander').AsCurrency;
end
else
begin
MinSpecsWidth:=850;
MaxSpecsWidth:=1600;
SingleMaxLong:=2300;
do
ubleMaxLong:=2380;
MaxSquander:=0.05;
end;
end;
end;
function ReturnAFull(ADividend,ADivisor:integer):integer;
begin
Result:=iif((ADividend mod ADivisor)=0,ADividend,ADividend+ADivisor-(ADividend mod ADivisor));
end;
procedure AssayMaterial(const AWaBie,AMaterial:string;ALong,AWidth,AHeight:double;
ProduceCount:integer;ARepeatFlag:boolean;var AllAcceptSpecs:TAcceptSpecs);
var
i1,TmpUsesLong,TmpUsesWidth,UsesLong,UsesWidth,UsesHeight,AllUsesCount,
UnitDivCount,TmpStockLong,TmpStockWidth,LongUsesCount,BestWidth:integer;
TmpQiPaoLongouble;
begin
UsesLong:=Round(ALong*10);
UsesWidth:=Round(AWidth*10);
UsesHeight:=Round(AHeight*10);
if Trim(AWaBie)='3' then
begin
if UsesHeight>0 then
begin
if (UsesWidth+UsesHeight)>1200 then
begin
TmpUsesWidth:=ReturnAFull((UsesWidth+UsesHeight) div 2,10);
LongUsesCount:=2;
end
else
begin
TmpUsesWidth:=ReturnAFull(UsesWidth+UsesHeight,10);
LongUsesCount:=1;
end;
end
else
begin
if UsesWidth*2>1200 then
begin
TmpUsesWidth:=ReturnAFull(UsesWidth,10);
LongUsesCount:=2;
end
else
begin
TmpUsesWidth:=ReturnAFull(2*UsesWidth,10);
LongUsesCount:=1;
end;
end;
TmpUsesWidth:=ReturnAFull(TmpUsesWidth,10);
SetLength(AllAcceptSpecs.AllAcceptResult,1);
AllAcceptSpecs.Areas:=(ProduceCount*ALong*TmpUsesWidth/10)*LongUsesCount;
AllAcceptSpecs.AllAcceptResult[0].QiPaoLong:=ProduceCount*ALong;
AllAcceptSpecs.AllAcceptResult[0].Long:=1;
AllAcceptSpecs.AllAcceptResult[0].Width:=TmpUsesWidth div 10;
with DmForm.QryPub1do
begin
Close;
Sql.Clear;
Sql.Add('select 库存数量 from 视图库存 where 瓦别代号=3 and 宽度='+IntToStr(AllAcceptSpecs.AllAcceptResult[0].Width));
Open;
if Fields[0].Value>=AllAcceptSpecs.AllAcceptResult[0].QiPaoLong then
begin
AllAcceptSpecs.IfAccept:=False;
AllAcceptSpecs.AllAcceptResult[0].Counts:=0;
end
else
begin
AllAcceptSpecs.IfAccept:=true;
TmpQiPaoLong:=(AllAcceptSpecs.AllAcceptResult[0].QiPaoLong-Fields[0].AsCurrency)*100;
AllAcceptSpecs.AllAcceptResult[0].Counts:=ReturnAFull(Round(TmpQiPaoLong),1200000) div 100;
end;
end;
Exit;
end;
GetUseLongWidth(AWaBie,AMaterial,UsesLong,UsesWidth,UsesHeight,ARepeatFlag,TmpUsesLong,TmpUsesWidth,LongUsesCount);
BestWidth:=GetBestWidth(TmpUsesWidth,UnitDivCount);
AllAcceptSpecs.Areas:=(TmpUsesLong div 10)*(BestWidth div 10)*(ReturnAFull(ProduceCount,UnitDivCount) div UnitDivCount)*LongUsesCount;
AllAcceptSpecs.LongUnitCount:=LongUsesCount;
if (iif(ProduceCount mod UnitDivCount=0,ProduceCount,ProduceCount+UnitDivCount-ProduceCount mod UnitDivCount) div UnitDivCount)>100 then
begin
SetLength(AllAcceptSpecs.AllAcceptResult,1);
AllAcceptSpecs.AllAcceptResult[0].Long:=TmpUsesLong div 10;
AllAcceptSpecs.AllAcceptResult[0].Width:=BestWidth div 10;
AllAcceptSpecs.AllAcceptResult[0].Counts:=(iif(ProduceCount mod UnitDivCount=0,ProduceCount,ProduceCount+UnitDivCount-ProduceCount mod UnitDivCount) div UnitDivCount)* LongUsesCount;
AllAcceptSpecs.AllAcceptResult[0].Counts:=iif((UnitDivCount div LongUsesCount>=1) and (LongUsesCount mod 2=0) and (ProduceCount mod 2<>0),AllAcceptSpecs.AllAcceptResult[0].Counts-(UnitDivCount div LongUsesCount),AllAcceptSpecs.AllAcceptResult[0].Counts);
AllAcceptSpecs.IfAccept:=True;
exit;
end;
ReadAllMaterial(AWaBie,AMaterial,TmpUsesLong,BestWidth);
UnitDivCount:=BestWidth div TmpUsesWidth;
if ProduceCount mod UnitDivCount=0 then
AllUsesCount:=(ProduceCount div UnitDivCount)*LongUsesCount
else
AllUsesCount:=((ProduceCount+(UnitDivCount-(ProduceCount mod UnitDivCount))) div UnitDivCount) * LongUsesCount;
for i1:=1 to High(AllSpecs)do
begin
TmpStockLong:=AllSpecs[i1].StockLong*10;
TmpStockWidth:=AllSpecs[i1].StockWidth*10;
if (TmpStockWidth<BestWidth) or (TmpStockLong<TmpUsesLong) then
begin
AllSpecs[i1].SquanderScale:=10000;
AllSpecs[i1].AllUsesCount:=10000;
Continue;
end
else
begin
AllSpecs[i1].SquanderScale:=(TmpStockWidth*TmpStockLong-BestWidth*TmpUsesLong)*1.0/(TmpStockWidth*TmpStockLong);
AllSpecs[i1].AllUsesCount:=AllUsesCount;
end;
end;
SortMaterial();
if not SetUsesEd(AllUsesCount,AllAcceptSpecs) then
begin
//应去订货。所有小于3%的规格总和不够生产该数量的产品
SetLength(AllAcceptSpecs.AllAcceptResult,1);
AllAcceptSpecs.AllAcceptResult[0].Long:=(TmpUsesLong div 10);
AllAcceptSpecs.AllAcceptResult[0].Width:=BestWidth div 10;
AllAcceptSpecs.AllAcceptResult[0].Counts:=(iif(ProduceCount mod UnitDivCount=0,ProduceCount,ProduceCount+UnitDivCount-(ProduceCount mod UnitDivCount)) div UnitDivCount) * LongUsesCount;
AllAcceptSpecs.AllAcceptResult[0].Counts:=iif((UnitDivCount div LongUsesCount>=1) and (LongUsesCount mod 2=0) and (ProduceCount mod 2<>0),AllAcceptSpecs.AllAcceptResult[0].Counts-(UnitDivCount div LongUsesCount),AllAcceptSpecs.AllAcceptResult[0].Counts);
AllAcceptSpecs.IfAccept:=True;
exit;
end;
end;
end.