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

很遗憾,这两天还是没找到图论中的网络流的解法.于是还是用搜索做了此题,做了一些优化.
先用贪心法求了一个可行解Better,做为初始的剪制枝条件.
对每一合法的新结点,做最乐观估计,如果还不比Better更优,则剪枝.
再对合法的新结点做最悲观估计,如果还比Better更优,则替换Better.
program Project1;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
MaxMaterialNum = 10;
MaxOrderNum = 40;
type
TUsedMaterial = record
MaterialNo: Integer;
UnUsedSize: Integer;
Orders: set of Byte
end;

TOrder = record
Size: Integer;
MaxWaster: Integer;
MaterialNo: Integer
end;

TNode = record
d: Integer;
UsedMaterial: array [1..MaxOrderNum] of TUsedMaterial;
UsedMaterialNum: Integer;
AllUnUsedSize: Integer
end;

var
Material: array [1..MaxMaterialNum] of Integer;
MaterialNum: Integer;
Order: array [1..MaxOrderNum] of TOrder;
OrderNum: Integer;
Stack: array [1..MaxOrderNum+1] of TNode;
Top: Integer;
NewNode: TNode;
do
ne: Boolean;
Better: TNode;
BestWaster: array [1..MaxOrderNum] of Integer;
WorstWaster: array [0..MaxOrderNum] of Integer;
procedure PackMaterial;
var
i, j: Integer;
t: Integer;
begin
i:=1;
while i<MaterialNumdo
begin
j:=i+1;
while j<=MaterialNumdo
begin
if Material=Material[j] then
begin
Material[j]:=Material[MaterialNum];
Dec(MaterialNum)
end;
Inc(j)
end;
Inc(i)
end;

for i:=1 to MaterialNum-1do
for j:=i+1 to MaterialNumdo
if Material>Material[j] then
begin
t:=Material;
Material:=Material[j];
Material[j]:=t
end
end;

procedure InitOrders;
var
i, j: Integer;
t: TOrder;
begin
for i:=1 to OrderNumdo
begin
j:=1;
while (Material[j]<Order.Size) and (j<=MaterialNum)do
Inc(j);
if j>MaterialNum then
begin
WriteLn('Not Found!');
ReadLn;
Halt
end;
Order.MaxWaster:=Material[j]-Order.Size;
Order.MaterialNo:=j
end;

for i:=1 to OrderNum-1do
for j:=i+1 to OrderNumdo
if Order.MaxWaster<Order[j].MaxWaster then
begin
t:=Order;
Order:=Order[j];
Order[j]:=t
end
end;

procedure InitBetter;
var
i, j: Integer;
do
ne: Boolean;
begin
BestWaster[1]:=0;
for i:=2 to OrderNumdo
BestWaster[1]:=BestWaster[1]+Order.Size;
for i:=2 to OrderNumdo
BestWaster:=BestWaster[i-1]-Order.Size;
Better.UsedMaterialNum:=1;
Better.UsedMaterial[1].MaterialNo:=Order[OrderNum].MaterialNo;
Better.UsedMaterial[1].UnUsedSize:=Order[OrderNum].MaxWaster;
Better.UsedMaterial[1].Orders:=[OrderNum];
Better.AllUnUsedSize:=Order[OrderNum].MaxWaster;
WorstWaster[OrderNum-1]:=Better.AllUnUsedSize;
for i:=OrderNum-1do
wnto 1do
begin
j:=1;
do
ne:=False;
while (j<=Better.UsedMaterialNum) and (notdo
ne)do
begin
if Order.Size<=Better.UsedMaterial[j].UnUsedSize then
begin
Better.UsedMaterial[j].UnUsedSize:=Better.UsedMaterial[j].UnUsedSize
-Order.Size;
Better.UsedMaterial[j].Orders:=Better.UsedMaterial[j].Orders+;
Better.AllUnUsedSize:=Better.AllUnUsedSize-Order.Size;
do
ne:=True
end
else
Inc(j)
end;
if notdo
ne then
begin
Inc(Better.UsedMaterialNum);
Better.UsedMaterial[Better.UsedMaterialNum].MaterialNo:=Order.MaterialNo;
Better.UsedMaterial[Better.UsedMaterialNum].UnUsedSize:=Order.MaxWaster;
Better.UsedMaterial[Better.UsedMaterialNum].Orders:=;
Better.AllUnUsedSize:=Better.AllUnUsedSize+Order.MaxWaster
end;
WorstWaster[i-1]:=Better.AllUnUsedSize
end
end;

procedure Init;
var
i: Integer;
begin
Write('Input Material Num: ');
ReadLn(MaterialNum);
for i:=1 to MaterialNumdo
begin
Write('Input Material[', i, '] Size:');
ReadLn(Material)
end;

Write('Input Order Num: ');
ReadLn(OrderNum);
for i:=1 to OrderNumdo
begin
Write('Input Order[', i, '] Size:');
ReadLn(Order.Size)
end;

PackMaterial;
InitOrders;
Top:=1;
with Stack[Top]do
begin
d:=0;
FillChar(UsedMaterial, SizeOf(UsedMaterial), 0);
UsedMaterialNum:=0;
AllUnUsedSize:=0
end;

InitBetter
end;

procedure Print(Node: TNode);
var
i, j: Integer;
begin
for i:=1 to Node.UsedMaterialNumdo
begin
Write(Material[Node.UsedMaterial.MaterialNo], ' :');
for j:=1 to OrderNumdo
if (j in Node.UsedMaterial.Orders) then
Write(' ', Order[j].Size);
WriteLn(' UnUsed Size=', Node.UsedMaterial.UnUsedSize)
end;
WriteLn('All UnUsed Size=', Node.AllUnUsedSize)
end;

begin
Init;
while Top>0do
begin
while Stack[Top].d<Stack[Top].UsedMaterialNum+MaterialNumdo
begin
do
ne:=False;
Inc(Stack[Top].d);
NewNode:=Stack[Top];
if NewNode.d<=NewNode.UsedMaterialNum then
begin
if Order[Top].Size<=NewNode.UsedMaterial[NewNode.d].UnUsedSize then
begin
NewNode.UsedMaterial[NewNode.d].UnUsedSize:=
NewNode.UsedMaterial[NewNode.d].UnUsedSize-Order[Top].Size;
NewNode.UsedMaterial[NewNode.d].Orders:=
NewNode.UsedMaterial[NewNode.d].Orders+[Top];
NewNode.AllUnUsedSize:=NewNode.AllUnUsedSize-Order[Top].Size;
do
ne:=True
end
end
else
begin
if Order[Top].Size<=Material[NewNode.d-NewNode.UsedMaterialNum] then
begin
Inc(NewNode.UsedMaterialNum);
NewNode.UsedMaterial[NewNode.UsedMaterialNum].MaterialNo:=
NewNode.d-NewNode.UsedMaterialNum+1;
NewNode.UsedMaterial[NewNode.UsedMaterialNum].UnUsedSize:=
Material[NewNode.UsedMaterial[NewNode.UsedMaterialNum].MaterialNo]
-Order[Top].Size;
NewNode.UsedMaterial[NewNode.UsedMaterialNum].Orders:=[Top];
NewNode.AllUnUsedSize:=NewNode.AllUnUsedSize
+NewNode.UsedMaterial[NewNode.UsedMaterialNum].UnUsedSize;
do
ne:=True
end
end;
ifdo
ne then
begin
if Top=OrderNum then
begin
if NewNode.AllUnUsedSize<Better.AllUnUsedSize then
Better:=NewNode
end
else
if ((NewNode.AllUnUsedSize-BestWaster[Top])<=Better.AllUnUsedSize) and (Top<OrderNum) then
begin
if (NewNode.AllUnUsedSize+WorstWaster[Top])<Better.AllUnUsedSize then
Better:=NewNode;
Inc(Top);
Stack[Top]:=NewNode;
Stack[Top].d:=0
end
end
end;
Dec(Top)
end;
if Better.UsedMaterialNum=0 then
WriteLn('Not Found!')
else
Print(Better);
ReadLn
end.
仅测试了几组数据,楼主请多测试一下.
可以把您的测试数据以及程序的运行结果和运行时间告诉我.
 
谢谢，我试试
 
to LeeChange
没有注释，太难理解了，能加上注释吗？
 
先告诉我结果怎么样.
 
呵呵，测试的结果怎么样呀?
你如果想知道程序的原理,就留下msn或QQ.
这样你一句我一句,明年也不一定讲的完.
 
原料12,15,34,67,89
需要材料8,5,6,7,8,14
得到结果：
12:5 6 used size=1
15:7 8 used size=0
all unused size=1
那14和8呢？
 
呵呵，找到Bug就好,我试试.
 
qq:82822198
 
LeeChange,真谢谢你，有结果了吗？要不用qq？
 
please wait...
 
这个Bug找到了.
将246行"if NewNode.AllUnUsedSize<Better.AllUnUsedSize then
"中的
"<"改为"<="就行了.
 
又发现了Bug.
将
if (NewNode.AllUnUsedSize+WorstWaster[Top])<Better.AllUnUsedSize then
Better:=NewNode;
改为
if (NewNode.AllUnUsedSize+WorstWaster[Top])<Better.AllUnUsedSize then
begin
Better:=NewNode;
Better.AllUnUsedSize:=Better.AllUnUsedSize+WorstWaster[Top]
end;
 
新程序全文如下:
program Project1;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
MaxMaterialNum = 10;
MaxOrderNum = 40;
type
TUsedMaterial = record
MaterialNo: Integer;
UnUsedSize: Integer;
Orders: set of Byte
end;

TOrder = record
Size: Integer;
MaxWaster: Integer;
MaterialNo: Integer
end;

TNode = record
d: Integer;
UsedMaterial: array [1..MaxOrderNum] of TUsedMaterial;
UsedMaterialNum: Integer;
AllUnUsedSize: Integer
end;

var
Material: array [1..MaxMaterialNum] of Integer;
MaterialNum: Integer;
Order: array [1..MaxOrderNum] of TOrder;
OrderNum: Integer;
Stack: array [1..MaxOrderNum+1] of TNode;
Top: Integer;
NewNode: TNode;
do
ne: Boolean;
Better: TNode;
BestWaster: array [1..MaxOrderNum] of Integer;
WorstWaster: array [0..MaxOrderNum] of Integer;
procedure PackMaterial;
var
i, j: Integer;
t: Integer;
begin
i:=1;
while i<MaterialNumdo
begin
j:=i+1;
while j<=MaterialNumdo
begin
if Material=Material[j] then
begin
Material[j]:=Material[MaterialNum];
Dec(MaterialNum)
end;
Inc(j)
end;
Inc(i)
end;

for i:=1 to MaterialNum-1do
for j:=i+1 to MaterialNumdo
if Material>Material[j] then
begin
t:=Material;
Material:=Material[j];
Material[j]:=t
end
end;

procedure InitOrders;
var
i, j: Integer;
t: TOrder;
begin
for i:=1 to OrderNumdo
begin
j:=1;
while (Material[j]<Order.Size) and (j<=MaterialNum)do
Inc(j);
if j>MaterialNum then
begin
WriteLn('Not Found!');
ReadLn;
Halt
end;
Order.MaxWaster:=Material[j]-Order.Size;
Order.MaterialNo:=j
end;

for i:=1 to OrderNum-1do
for j:=i+1 to OrderNumdo
if Order.MaxWaster<Order[j].MaxWaster then
begin
t:=Order;
Order:=Order[j];
Order[j]:=t
end
end;

procedure InitBetter;
var
i, j: Integer;
do
ne: Boolean;
begin
BestWaster[1]:=0;
for i:=2 to OrderNumdo
BestWaster[1]:=BestWaster[1]+Order.Size;
for i:=2 to OrderNumdo
BestWaster:=BestWaster[i-1]-Order.Size;
Better.UsedMaterialNum:=1;
Better.UsedMaterial[1].MaterialNo:=Order[OrderNum].MaterialNo;
Better.UsedMaterial[1].UnUsedSize:=Order[OrderNum].MaxWaster;
Better.UsedMaterial[1].Orders:=[OrderNum];
Better.AllUnUsedSize:=Order[OrderNum].MaxWaster;
WorstWaster[OrderNum-1]:=Better.AllUnUsedSize;
for i:=OrderNum-1do
wnto 1do
begin
j:=1;
do
ne:=False;
while (j<=Better.UsedMaterialNum) and (notdo
ne)do
begin
if Order.Size<=Better.UsedMaterial[j].UnUsedSize then
begin
Better.UsedMaterial[j].UnUsedSize:=Better.UsedMaterial[j].UnUsedSize
-Order.Size;
Better.UsedMaterial[j].Orders:=Better.UsedMaterial[j].Orders+;
Better.AllUnUsedSize:=Better.AllUnUsedSize-Order.Size;
do
ne:=True
end
else
Inc(j)
end;
if notdo
ne then
begin
Inc(Better.UsedMaterialNum);
Better.UsedMaterial[Better.UsedMaterialNum].MaterialNo:=Order.MaterialNo;
Better.UsedMaterial[Better.UsedMaterialNum].UnUsedSize:=Order.MaxWaster;
Better.UsedMaterial[Better.UsedMaterialNum].Orders:=;
Better.AllUnUsedSize:=Better.AllUnUsedSize+Order.MaxWaster
end;
WorstWaster[i-1]:=Better.AllUnUsedSize
end
end;

procedure Init;
var
i: Integer;
begin
Write('Input Material Num: ');
ReadLn(MaterialNum);
for i:=1 to MaterialNumdo
begin
Write('Input Material[', i, '] Size:');
ReadLn(Material)
end;

Write('Input Order Num: ');
ReadLn(OrderNum);
for i:=1 to OrderNumdo
begin
Write('Input Order[', i, '] Size:');
ReadLn(Order.Size)
end;

PackMaterial;
InitOrders;
Top:=1;
with Stack[Top]do
begin
d:=0;
FillChar(UsedMaterial, SizeOf(UsedMaterial), 0);
UsedMaterialNum:=0;
AllUnUsedSize:=0
end;

InitBetter
end;

procedure Print(Node: TNode);
var
i, j: Integer;
begin
for i:=1 to Node.UsedMaterialNumdo
begin
Write(Material[Node.UsedMaterial.MaterialNo], ' :');
for j:=1 to OrderNumdo
if (j in Node.UsedMaterial.Orders) then
Write(' ', Order[j].Size);
WriteLn(' UnUsed Size=', Node.UsedMaterial.UnUsedSize)
end;
WriteLn('All UnUsed Size=', Node.AllUnUsedSize)
end;

begin
Init;
while Top>0do
begin
while Stack[Top].d<Stack[Top].UsedMaterialNum+MaterialNumdo
begin
do
ne:=False;
Inc(Stack[Top].d);
NewNode:=Stack[Top];
if NewNode.d<=NewNode.UsedMaterialNum then
begin
if Order[Top].Size<=NewNode.UsedMaterial[NewNode.d].UnUsedSize then
begin
NewNode.UsedMaterial[NewNode.d].UnUsedSize:=
NewNode.UsedMaterial[NewNode.d].UnUsedSize-Order[Top].Size;
NewNode.UsedMaterial[NewNode.d].Orders:=
NewNode.UsedMaterial[NewNode.d].Orders+[Top];
NewNode.AllUnUsedSize:=NewNode.AllUnUsedSize-Order[Top].Size;
do
ne:=True
end
end
else
begin
if Order[Top].Size<=Material[NewNode.d-NewNode.UsedMaterialNum] then
begin
Inc(NewNode.UsedMaterialNum);
NewNode.UsedMaterial[NewNode.UsedMaterialNum].MaterialNo:=
NewNode.d-NewNode.UsedMaterialNum+1;
NewNode.UsedMaterial[NewNode.UsedMaterialNum].UnUsedSize:=
Material[NewNode.UsedMaterial[NewNode.UsedMaterialNum].MaterialNo]
-Order[Top].Size;
NewNode.UsedMaterial[NewNode.UsedMaterialNum].Orders:=[Top];
NewNode.AllUnUsedSize:=NewNode.AllUnUsedSize
+NewNode.UsedMaterial[NewNode.UsedMaterialNum].UnUsedSize;
do
ne:=True
end
end;
ifdo
ne then
begin

if Top=OrderNum then
begin
if NewNode.AllUnUsedSize<=Better.AllUnUsedSize then
Better:=NewNode
end
else
if ((NewNode.AllUnUsedSize-BestWaster[Top])<=Better.AllUnUsedSize) and (Top<OrderNum) then
begin
if (NewNode.AllUnUsedSize+WorstWaster[Top])<Better.AllUnUsedSize then
begin
Better:=NewNode;
Better.AllUnUsedSize:=Better.AllUnUsedSize+WorstWaster[Top]
end;
Inc(Top);
Stack[Top]:=NewNode;
Stack[Top].d:=0
end
end
end;
Dec(Top)
end;
if Better.UsedMaterialNum=0 then
WriteLn('Not Found!')
else
Print(Better);
ReadLn
end.
 
昆明找我....
 
我可能这一两天会去，不过想来也不会得到什么好招待了，因为我是没给你提供什么帮助
却占用了很多的空间及时间。[:(][:(][:(][:(]
开个玩笑，不过这一两天就要到昆明去了，希望能成为朋友。大家共同进步！
 
to：ReallyFail，真的？
来就联系我，虽然寒舍太差，不过有个很好的媳妇在家，记住给我电话tel:0871-5511508
一定要！！！我姓“成”，下班时间都在，如果不下班，有我老婆在,她会告诉我的....
 
..................
 
洛吉：
可以了吗？我也正需要这个算法。。。不过，我所需的只有一种原材料。
noall@163.com
 
LeeChange：能写上一些注释吗？
 
to noall
可以使用，不过材料只能在15以下，否则运算时间太长
你是一种原料，那就更简单了
 
您必须登录或注册才可回复。

Similar threads

I
微软面试试题精选
回复
0
查看
605
import
I
I
常用算法（1）贪婪算法
回复
0
查看
617
import
I
I
常用算法（2）分而治之算法
回复
0
查看
668
import
I
I
常用算法（3）动态规划
回复
0
查看
865
import
I
I
常用算法（5）分枝定界
回复
0
查看
583
import
I
顶部