LeeChange请进，请教您材料最省那个题目的程序(200分)

呵呵，继续拜读您的程序,感谢您对我的帮助!
材料最省的优化算法
条件：
1、有不同长度的标准规格材料
2、需要不同长度的材料
问题：
用这些标准规格的材料截出所有需要的材料，
如何得到最省材料的切割方法？
您的讲解与程序如下:
先用贪心法求了一个可行解Better,做为初始的剪制枝条件.
对每一合法的新结点,做最乐观估计,如果还不比Better更优,则剪枝.
再对合法的新结点做最悲观估计,如果还比Better更优,则替换Better.
这个程序比较有意思，但程序很长，看不懂的地方更多，能不能在这个程序中加点注释??
比如Stack[Top].d中d是什么意思，而 Stack[Top].d<Stack[Top].UsedMaterialNum+MaterialNum 中
Stack[Top].UsedMaterialNum+MaterialNum是什么意思？
还有各个重要的if语句分布是判断什么？
我很想读懂这个程序，请Leechange帮帮我。
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.

while Stack[Top].d<Stack[Top].UsedMaterialNum+MaterialNumdo
//Stack[Top].UsedMaterialNum:当前结点已经用了多少根原料
//MaterialNum:原料总数
//两者相加就是一根材料用哪根原料或者用一根新原料的所有可能选择
begin
...
if if Order[Top].Size<=NewNode.UsedMaterial[NewNode.d].UnUsedSize then

//用已经使用过的剩余原料加工当前材料
else
//用新原料加工当前材料
...
end

谢谢您的解答，再问两个地方：
1)
...
if Order[Top].Size<=Material[NewNode.d-NewNode.UsedMaterialNum] then
...
NewNode.d是在遍历“一根材料用哪根原料或者用一根新原料的所有可能选择”吗？
呵呵，还是不好理解这个Newnode.d，这里NewNode.d-NewNode.UsedMaterialNum又是
怎么意思？麻烦您再给我解释一下（NewNode.d？）？
2)if (NewNode.AllUnUsedSize+WorstWaster[Top])<Better.AllUnUsedSize then
...
就是您前面说的“对合法的新结点做最悲观估计,如果还比Better更优,则替换Better.
”吧，但是这里不好理解WorstWaster这个数组到底存放的什么东西，是怎么计算出来的。
(不好意思，前面WorstWaster数组的产生没有看懂)，还要有劳您解释一下这个地方。
谢谢您的帮助！

--NewNode.d是在遍历“一根材料用哪根原料或者用一根新原料的所有可能选择”吗？
是.
--NewNode.d-NewNode.UsedMaterialNum又是怎么意思？麻烦您再给我解释一下NewNode.d？）？
NewNode.d决定了当前要加工的材料使用哪一根原料.
当NewNode.d<=NewNode.UsedMaterialNum时表示使用已经用过的原料,NewNode.d的数值就是要使用的已使用过的原料.
当NewNode.d>NewNode.UsedMaterialNum时表示使用一根新的原料,NewNode.d-NewNode.UsedMaterialNum就是要使用的新原料的编号.
--但是这里不好理解WorstWaster这个数组到底存放的什么东西，是怎么计算出来的。
代码我自己没有保存,你也没贴出WorstWaster的计算部分,我想应该是所有未加工过的材料用比较浪费的方法(比如一根原料只加工一根材料)时所产生的废料的总和.

Sorry,我不知道您没有保存代码，下面我贴出来
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;
希望您再解释一下WorstWater数组的意义以及用处。
谢谢！

先说一下上面的代码对Better的处理是用贪心法求一个可行解.
WorstWaster就是在求出Better的基础上算出来的,他就是在Better这个可行解中放过前i个物品后还需要浪费多少空间才能全部放完.
严格意义上说,他不是准确的最悲观估计,但是当前浪费+WorstWaster肯定比实际的最优解的浪费要大,所以用if (NewNode.AllUnUsedSize+WorstWaster[Top])<Better.AllUnUsedSize then
剪枝不会丢失最优解.

懂了，谢谢！