求解一最优分割算法,是不是太多的开发工具让大家不再专注于算法研究了...... (300分)

设一批基本钢管长为L
要分割为一批长度如下的钢管
长度为N1,数量为Q1
长度为N2,数量为Q2
.................
长度为Nx,数量为Qx
N1....Nx中任意一个数不会大于L
求领取基本钢管的最佳方案(即什么样的方案领料最省)

是不是太多的开发工具让大家不再专注于算法研究了,就像我一样,做了几年的
数据库,居然连基本算法都不记得了,只要请大家帮帮忙,提供点思路或方法,我
都可能有很大的启发,拜托各位,分不够可以再加!

问题不是很明确，没有说出领料的条件，最省的条件。
这是一个数学最优化算法 -- 有这个课程 的问题，找本书看看先。

to 叶不归:
领料的条件就是根据要求的分割的钢管去领取基本钢管再进行分割,以领取的基件管
数量最少认定为最省料

还真有点难，很少考虑算法了

研究一下背包算法，另外，好像有人用遗传算法解决，记不得在那里看的资料了

难道大家真的都不理算法了吗?
to tseung:
背包算法不可吧,遗传记算法可以吗?说说看吧
to 叶不归
书找到了吗?
兄弟们,帮帮手呀,我好急

基本钢管长为定值L，当然可以用背包算法，
包的容量是L。

TO jiangxiancheng
我也考虑过背包问题,问题是背包问题求的是一个最佳解,而我要求的是把所有
料用完,我试过用递归的方法来调用背包问题,充其量只是一个贪婪算法,并不能
得到所有方案的最佳解

这是一道运筹学上的问题阿!
回去看看在来回答

确实是一份数学规划，你只要能把约束写出来，就可以用单纯形算法求解的

昨天晚上在床上想了一下，虽然我不知道什么背包问题，但还是把它写出来了，我觉得你的
的问题还是有点不明确，所以只能写一个下面的例子，给你看一下，已经通过验证，给分吧!
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls;
type
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
procedure Button1Click(Sender: TObject);
procedure pro(sender:tobject;L:integer);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;
type
TGLrecored=record
GLleng:integer;
GLcount:integer;
end;
var
GLarray:array[1..10] of TGLrecored;
//我们假设所有的钢管的类型，数量都放在这个数组中;
implementation
{$R *.DFM}
procedure TForm1.Button1Click(Sender: TObject);
var L:integer;
begin
GLarray[1].GLleng:=5;
GLarray[1].GLcount:=600;
GLarray[2].GLleng:= 10;
GLarray[2].GLcount:=50;
GLarray[3].GLleng:=12;
GLarray[3].GLcount:=60;
GLarray[4].GLleng:=13;
GLarray[4].GLcount:=111;
GLarray[5].GLleng:=17;
GLarray[5].GLcount:=10;
GLarray[6].GLleng:=24;
GLarray[6].GLcount:=34;
GLarray[7].GLleng:=30;
GLarray[7].GLcount:=4;
GLarray[8].GLleng:=40;
GLarray[8].GLcount:=56;
GLarray[9].GLleng:=47;
GLarray[9].GLcount:=7;
GLarray[10].GLleng:=60;
GLarray[10].GLcount:=2;
{必须要先对GLayyay这个数组按GLleng排序，我们假设已经排过了。}
L:=400;
//这个L就是你问题中的那个L
pro(sender,L);
end;

procedure TForm1.pro(sender: tobject;
L: integer);
var
i,j:integer;
begin
i:=1;
while (i<=10) and (GLarray.GLleng<L) and (Glarray.GLcount<>0)do
begin
inc(i);
end;
if i=1 then
inc(i);
if GLarray[i-1].GLcount<L div GLarray[i-1].GLleng then
begin
j:=GLarray[i-1].GLcount;
GLarray[i-1].GLcount:=0;
end
else
j:=L div GLarray[i-1].GLleng;
memo1.Lines.Add('需要第'+inttostr(i-1)+'种型号钢管'+inttostr(j)+'根。');
L:=L-GLarray[i-1].GLleng*j;
ShowMessage(inttostr(l));
if L>0 then
pro(sender,L);

end;

end.

把 ShowMessage(inttostr(l));
这行去掉。

To 张辉明
张兄,先说声谢谢,再说声对不起!
张兄,你实际上写出的应该可以认为是类背包问题的方案,
但还不及背包问题复杂,而实际上,我的要求比背包问题还要复
杂很多,你所提到的方案中可以不用递归实现,而我用你的这种
方案作为一个子过程,可以构架出一个"贪婪算法",但这并不符
合我的要求,我要得到的并不是用给定的GLarray[1]..GLarray[10]
来分一条L出来,而是要用x条L来分出GLarray[1]..GLarray[10],
便得x最小的方案,
假如我有一批6米长的管
需求0.5米长的管12根
5.5米长的管12根
那最佳方案很容易得出:
(0.5+5.5) * 12
总共需求6米长的管 12支
而用你的方案作为子过程构架出的"贪婪算法"可能得到:
(0.5*12) * 1
5.5 * 12
总共需求6米长的管 1+12=13支
可见贪婪算法并不符合要求,难点不在于得到第一个最佳组合,
而是所有组合中的最佳方案
请大家继续出谋划策

是呀，我把问题看错了，不好意思了，现在我知道你的意思了，
下面这个绝对可以达到你的要求了。唉！现在已经半夜了。不过暑假在家，学学delphi也
非常有意思呀，真的希望快些毕业呀！　：P

unit Unit1;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
procedure Button1Click(Sender: TObject);
procedure pro(sender:tobject;L:integer);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;
type
TGLrecored=record
GLleng:integer;
GLcount:integer;
end;
var
GLarray:array[1..10] of TGLrecored;
//我们假设所有的钢管的类型，数量都放在这个数组中;
implementation
{$R *.DFM}
procedure TForm1.Button1Click(Sender: TObject);
var L,i,j,LCount:integer;
begin
GLarray[1].GLleng:=5;
GLarray[1].GLcount:=23;
GLarray[2].GLleng:= 10;
GLarray[2].GLcount:=13;
GLarray[3].GLleng:=12;
GLarray[3].GLcount:=60;
GLarray[4].GLleng:=13;
GLarray[4].GLcount:=11;
GLarray[5].GLleng:=17;
GLarray[5].GLcount:=10;
GLarray[6].GLleng:=24;
GLarray[6].GLcount:=34;
GLarray[7].GLleng:=30;
GLarray[7].GLcount:=4;
GLarray[8].GLleng:=40;
GLarray[8].GLcount:=56;
GLarray[9].GLleng:=47;
GLarray[9].GLcount:=7;
GLarray[10].GLleng:=60;
GLarray[10].GLcount:=2;
j:=1;
LCount:=0;
{必须要先对GLayyay这个数组按GLleng排序，我们假设已经排过了。}
L:=100;
//这个L就是你问题中的那个L
while j<>0do
begin
inc(LCount);
pro(sender,L);
//开始分割一个L型号的管子 。
i:=1;
j:=0;
while i<=10do
begin
j:=j+GLarray.GLcount;
inc(i);
end;

end;
ShowMessage('经过计算至少需要：'+inttostr(LCount)+'个L型号的管子');
end;

procedure TForm1.pro(sender: tobject;
L: integer);//如果你要打印每一个管子的细分过程，只要在这个过程中添加代码
var
i,j:integer;
begin
i:=10;
while (i>0) and (GLarray.GLcount=0) or (L<GLarray.GLleng)do
i:=i-1;
if i<>0 then
begin
j:=L div Glarray.GLleng;
if j>GLarray.GLcount then
begin
j:=GLarray.GLcount;
GLarray.GLcount:=0;
end
else
GLarray.GLcount:=GLarray.GLcount-j;
L:=L-GLarray.GLleng*j;
if L>GLarray[1].GLleng then
pro(sender,L);
end;

end;

end.

我还是用的上次的算法，在你上面举的这个例子中：
如果L是60
需要　5米　　12根
　　　55米　　12根
那我的程序肯定是：X=12;而不是13。
希望试你一下

To 张辉明:
原来你赋闲在家,先奉劝你一句,先不要一心想着外面,好好把基础打好,
出来了会有用的.
我不是说你的算法得到的结果是13,而是说贪婪算法得到的结果可能是13
也可能是12,这取决于取答案的先后顺序,只要是没有很好的统筹思想,都有可
能出现这种情况.我现在要得到的是一个很好统筹方案,看来还要好好想想才行,
不一定要源程序,有好的思路就行,源码还是我自已动手好了,贴在这太长了.
欢迎在校的科班生来帮忙,你们可能比我们这些在外打工的于算法方面更
有方法一些.

我不能保证我的算法求出的X是最小的。在巧合的时候，就会多出一根钢管来的。
例如：在下面的比较巧合的数组中：
GLarray[1].GLleng:=5;
GLarray[1].GLcount:=12;
GLarray[2].GLleng:= 11;
GLarray[2].GLcount:=12;
GLarray[3].GLleng:=24;
GLarray[3].GLcount:=12;
GLarray[4].GLleng:=27;
GLarray[4].GLcount:=12;
GLarray[5].GLleng:=29;
GLarray[5].GLcount:=12;
GLarray[6].GLleng:=33;
GLarray[6].GLcount:=12;
GLarray[7].GLleng:=35;
GLarray[7].GLcount:=12;
GLarray[8].GLleng:=36;
GLarray[8].GLcount:=12;
GLarray[9].GLleng:=47;
GLarray[9].GLcount:=0;
GLarray[10].GLleng:=60;
GLarray[10].GLcount:=0;
在L=100的时候。最佳算法的结果应该为24，而上面的结果是25
知道问题我们就可以想办法了，我们在每分割一个L时候，都要在GLarray.GLCountr<>0中找
GLarray.GLleng*x+GLarry[j]*y+GLarray[n]*z的最接近L的组合，这样我们求出来的X就能保证
是最小的了。如果我做出来了，就再贴出让大家参考一下，试试看吧。

我不想再考虑这个问题了，我觉得比背包问题还要
难得多，看看好像不难，其实比较伤脑细胞，
我只是把对这个问题我的看法，给大家参考一下:
虽然我可以把每次细分L的最接近L的组合求出来，
拿怕，求出数个组合正好等于L的长度，也不能保证
这次组合是正确的。还要考虑到i-1次的组合，跟L的
接近程度，而i-1次的组合，又要联系到i-2次，...
唉!菜鸟，就是菜鸟，不会就是不会。

给出一个笨办法：
1、给每根所要的钢管编号，如
长度为N1,数量为Q1—>得到N11，N12， N13...N1Q1
长度为N2,数量为Q2—>得到N21，N22， N23...N2Q2
.................
长度为Nx,数量为Qx—>得到NX1，NX2， NX3...NXQX
2、对所有的钢管求组合。
3、把求得的组合串如（N11， N12， N53， NX2...）转化成长度的串，如（Q1， Q1， Q5， QX...）
4、用L挨个儿减这些数，当结果小于零时，记一根钢管，重新减。
如：长度串为Q = （2，5，6，8，4，3，2，4，3，1，7，3，8，2...）， L为10
sl := 0;//sl表示数量
repeat
l := 10;
repeat
inc(i);
l := l - q;
until l - q[i + 1] < 0
inc(sl)
until i = 总根数
5、比较所有的sl，得到最小值。