还问哪.这是求最优解的代码.
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.
