几年前就这个问题请教过一个数学硕士，他告诉了我数学方法，但对于将实际问题转化为的数学公式，需要通过国外软件才可以解那个方程（收费的软件）。于是我现在在转换为数学公式的基础上，用自己的方式来解答，虽然不是最优方法，经过几种测试数据，发现，应该可以使用该方法。unit Unit1;interfaceuses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls;const SOURCELEN = 6000;type ArrayInt = array of Integer;
_OneMay = record Value: ArrayInt;
Count: Integer;
end;
_NeedInfo = record Length: do
uble;
//长度 NeedNum: Integer;
//需要的数量 end;
ArrNeed = array of _NeedInfo;
TForm1 = class(TForm) Button1: TButton;
Memo1: TMemo;
procedure Button1Click(Sender: TObject);
private FReqArr: ArrNeed;
FMay: array of _OneMay;
FOneComb: ArrayInt;
procedure SortData;
//对数据从大到小排序 procedure CalcData;
procedure DispData;
procedure Calc_AddMaybe(Index: Integer);
public { Public declarations } end;
var Form1: TForm1;implementation{$R *.dfm}uses Math;procedure TForm1.Button1Click(Sender: TObject);
begin
SetLength(FReqArr, 5);
FReqArr[0].Length := 1185;
FReqArr[0].NeedNum := 4;
FReqArr[1].Length := 1079;
FReqArr[1].NeedNum := 6;
FReqArr[2].Length := 985;
FReqArr[2].NeedNum := 10;
FReqArr[3].Length := 756;
FReqArr[3].NeedNum := 8;
FReqArr[4].Length := 500;
FReqArr[4].NeedNum := 5;{ SetLength(FReqArr, 3);
FReqArr[0].X := 3500;
FReqArr[0].Y := 12;
FReqArr[1].X := 3000;
FReqArr[1].Y := 5;
FReqArr[2].X := 2000;
FReqArr[2].Y := 13;
} SortData;
CalcData;
DispData;
end;
procedure TForm1.CalcData;var TmpReq: ArrNeed;
iLoop: Integer;
function _Diff(AWay: _OneMay): do
uble;
var I, C: Integer;
begin
Result := SOURCELEN;
for I := Low(TmpReq) to High(TmpReq) do
begin
if TmpReq.NeedNum = 0 then
Continue;
C := Min(AWay.Value, TmpReq.NeedNum);
Result := Result - C * TmpReq.Length;
//没有考虑整除 end;
end;
//处理第AIndex选取问题 procedure Search(ReqIndex: Integer);
var I: Integer;
MayCount: Integer;
MaxCount, MinIndex: Integer;
MinDiff, Tmp: do
uble;
Way: _OneMay;
begin
MinDiff := SOURCELEN;
MayCount := 0;
for I := Low(FMay) to High(FMay) do
begin
if FMay.Count > 0 then
Continue;
if FMay.Value[ReqIndex] = 0 then
Continue;
Inc(MayCount);
Tmp := _Diff(FMay);
if Tmp < MinDiff then
begin
MinDiff := Tmp;
MinIndex := I;
end;
end;
Way := FMay[MinIndex];
//计算MaxCount if MayCount = 1 then
MaxCount := Ceil(TmpReq[ReqIndex].NeedNum / Way.Value[ReqIndex]) else
begin
MaxCount := TmpReq[ReqIndex].NeedNum;
for I := Low(Way.Value) to High(Way.Value) do
begin
if TmpReq.NeedNum = 0 then
Continue;
if Way.Value = 0 then
Continue;
MaxCount := Min(MaxCount, Floor(TmpReq.NeedNum / Way.Value));
end;
end;
if MaxCount <= 0 then
MaxCount := 1;
//扣减数据 FMay[MinIndex].Count := MaxCount;
for I := Low(TmpReq) to High(TmpReq) do
TmpReq.NeedNum := Max(TmpReq.NeedNum - MaxCount * Way.Value, 0);
end;
begin
SetLength(FMay, 0);
SetLength(FOneComb, Length(FReqArr));
for iLoop := 0 to Trunc(SOURCELEN / FReqArr[0].Length) do
begin
FOneComb[0] := iLoop;
Calc_AddMaybe(1);
end;
SetLength(TmpReq, Length(FReqArr));
for iLoop := Low(FReqArr) to High(FReqArr) do
TmpReq[iLoop] := FReqArr[iLoop];
iLoop := 0;
while iLoop <= High(TmpReq) do
begin
if TmpReq[iLoop].NeedNum > 0 then
Search(iLoop);
if TmpReq[iLoop].NeedNum = 0 then
Inc(iLoop);
end;
end;
procedure TForm1.Calc_AddMaybe(Index: Integer);var K, H: Integer;
Lost: do
uble;
begin
Lost := SOURCELEN;
for K := 0 to Index - 1 do
Lost := Lost - FOneComb[K] * FReqArr[K].Length;
if Index = High(FOneComb) then
begin
FOneComb[Index] := Trunc(Lost / FReqArr[Index].Length);
SetLength(FMay, Length(FMay) + 1);
h := High(FMay);
SetLength(FMay[H].Value, Length(FOneComb));
FMay[H].Count := 0;
for K := Low(FOneComb) to High(FOneComb) do
begin
FMay[H].Value[K] := FOneComb[K];
if FOneComb[K] = 0 then
Continue;
end;
end else
begin
for K := 0 to Trunc(Lost / FReqArr[Index].Length) do
begin
FOneComb[Index] := K;
Calc_AddMaybe(Index + 1);
end;
end;
end;
procedure TForm1.DispData;var iLoop, J, iCount: Integer;
iDiff: do
uble;
sMess: string;
begin
//显示结果 Memo1.Lines.Clear;
sMess := format('材料长度：%d', [SOURCELEN]);
Memo1.Lines.Add(sMess);
sMess := '';
for J := Low(FReqArr) to High(FReqArr) do
sMess := sMess + Format('%-8f', [FReqArr[J].Length]);
Memo1.Lines.Add(sMess + ' <==短木头长度信息');
sMess := '';
for J := Low(FReqArr) to High(FReqArr) do
sMess := sMess + Format('%-8d', [FReqArr[J].NeedNum]);
Memo1.Lines.Add(sMess + ' <==短木头需要的数量');
Memo1.Lines.Add('');
Memo1.Lines.Add('=======将6000切割为不同长度的短木头，下面显示每种切割方式中，各种短木头的根数======');
Memo1.Lines.Add('=======需要多种方式切割才比较完善======');
iCount := 0;
;
for iLoop := High(FMay) do
wnto Low(FMay) do
begin
if FMay[iLoop].Count = 0 then
Continue;
iCount := iCount + FMay[iLoop].Count;
sMess := '';
for J := Low(FMay[iLoop].Value) to High(FMay[iLoop].Value) do
begin
sMess := sMess + Format('%-8d', [FMay[iLoop].Value[J]]);
end;
sMess := sMess + Format('当前切割方法数：%-3d', [FMay[iLoop].Count]);
Memo1.Lines.Add(sMess);
end;
iDiff := 0;
for iLoop := Low(FReqArr) to High(FReqArr) do
iDiff := iDiff + FReqArr[iLoop].Length * FReqArr[iLoop].NeedNum;
sMess := Format('所有短木相加的长度：%-5f', [iDiff]);
Memo1.Lines.Add(sMess);
sMess := Format('实际耗费长度：%d* %d = %d', [SOURCELEN, iCount, iCount * SOURCELEN]);
Memo1.Lines.Add(sMess);
sMess := Format('总浪费长度：%d - %f = %-5f', [iCount * SOURCELEN, iDiff, iCount * SOURCELEN - iDiff]);
Memo1.Lines.Add(sMess);
end;
procedure TForm1.SortData;var I, J, K: Integer;
t: _NeedInfo;
begin
for I := Low(FReqArr) to High(FReqArr) - 1 do
begin
K := I;
for J := I + 1 to High(FReqArr) do
if FReqArr[J].Length >= FReqArr[K].Length then
K := J;
if K <> I then
begin
t := FReqArr;
FReqArr := FReqArr[K];
FReqArr[K] := t;
end;
end;
end;
end.
=====================结果========材料长度：60001185.00 1079.00 985.00 756.00 500.00 <==短木头长度信息4 6 10 8 5 <==短木头需要的数量=======将6000切割为不同长度的短木头，下面显示每种切割方式中，各种短木头的根数=============需要多种方式切割才比较完善======4 0 0 1 1 当前切割方法数：1 0 3 2 1 0 当前切割方法数：1 0 3 0 1 4 当前切割方法数：1 0 0 5 1 0 当前切割方法数：1 0 0 3 4 0 当前切割方法数：1 所有短木相加的长度：29612.00实际耗费长度：6000* 5 = 30000总浪费长度：30000 - 29612.00 = 388.00
