To 数据结构版主 creation-zy, 张剑波 ===算法问题(200分)

程序自动生成一个数组，数据个数在20到50个（随机），数据类型为decimal,范围从0到50000,小数点后保留两位。指定一个数值，程序从数组中筛选出一部分数,使其和与指定的数值最接近，但不大于此数，筛选过程写成一个函数。
且测试:
随机数 时间
20个数 = 毫秒级
50个数 = 100秒
100个数 = 死机
详细请看:
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1016791

>>数据类型为decimal,范围从0到50000,小数点后保留两位。
可以被转化为0..5000000的整数。
既然您已经看过了 http://www.delphibbs.com/delphibbs/dispq.asp?lid=1016791 ...
我试验了一下，将随机数的最大值调整为5000000，目标和值定为123456789，在绝大多数
情况下（占80%吧）均可以在数秒以内得到最优解，在少数情况下，得到123456XXX之后就陷
入长时间循环（超过100秒——CPU：P4 1.6A）。
对于算法本身，我认为除非改变思路，否则不会有太大的性能提升。可以看出，这个算法
是一个NP复杂问题，因此，在数据量很大的情况下耗用很长的时间是很正常的。
由于我的算法是一个逐渐逼近的过程，因此，我认为，可以在程序中加入时间限制，在超
过时限时，就结束穷举，将已经得到的、非常接近最优解的结果取出（可以看出，在有限时
间内得到的次优解比最优解只差不到十万分之一：(0..789)/123456000）。
为了达到这个效果，只要在FindLeft过程中加入时间判断，一旦超过指定时间，就用Abort
强行退出（注意到在递规主体中调用系统时间API比较费时，可以采用递规上千次检查一次
用时的方法。

原来是一年前的事情了，
这个算法，实际上还有一点可以优化的余地，
比如采用查表比较法（或改进型折半搜索法）------不过要增加5MByte内存,[]
将判断条件写入循环体以减少子程序调用操作等。
但正如creation-zy兄所说，
要求最优解几乎不可能有质的飞跃。算法的复杂性是 O(n!/(K^n)),K随着情况不同而变化。
creation-zy兄的约束条件是挑选的元素必须小于余下的差值，
这个条件在随机数非常接近的时候将产生非常可怕的结果，(这时候K变得非常小)
即约束条件几乎无效（而且还增加了一点开销）。
btw:当时我刚刚进入论坛，说起话来带点火，可是creation-zy兄也很厉害[]，
居然串通张剑波斑竹把我探讨排地雷的100point分掉了。[]

[]

>>排地雷...串通...
天地良心呀！
我也觉得那个帖子张兄结贴的时间早了些——我一般只处理闲置2个月以上的帖子的...

很奇怪——我在家里的机器上（配置：毒龙1800+,256M DDR333）进行50个数的组合计算
——没有一次用时超过5秒的，全部都得到了理论最接近值。回到单位以后，用P4 1.6A，速
度慢了不说，经常还不能在20秒之内穷举完毕...
>>查表比较法
我想不出来如何使用，因为这涉及到在变化的集合中查找和为指定值的组合，复杂度非常
大，我认为可能有问题。还请DarwinZhang兄大致描述一下算法原理/流程。

我想DarwinZhang兄所谓的查表估计是把所有可能的和生成一个数组吧，
这样可以减少一些重复求和的时间，不过也不能一次性解决问题吧？

to beta兄：
我已经想过了。如果说将所有的可能和值计算出来，结果数量应该与“从50个数中任取25
个数的组合”的大小在一个数量级上（或者更大）——这恐怕不是5M(5G?)内存可以摆平的
问题吧（偶计算了一下光是C(50,25)，就有1.26E+14了！）。
如果我们对数据进行分组，比如将50个数字分成N个集合（各个集合包含的元素数量尽量
相等，设包含元素最多的集合的元素数量为M），然后问题就可以被分解为：从每个集合中
取出0到M个元素，使得它们的和最接近给定数。
若取N=10，则M为5，每个集合均可以生成 1+5+10+10+5+1=32 个结果（包含了一个都不取
以及全取的情况）。那么，从10个集合中进行取和的可能组合就有 32^10=1.12E+15 种可能
！！
若总共有49个元素，N=M=7，最终结果为 128^7=5.629E+14...
根据上面的计算，我认为，对于50或者50以上的情况，穷举是不可行的。不过，对于分组
之后的集合和值，倒是可以用我的算法思路进行计算，也许会提速若干个数量级...

听

creation-zy 兄的算法造诣果然是登峰造极，小弟佩服。

to creation-zy兄：
1."查表比较法...我想不出来如何使用，因为这涉及到在变化的集合中查找和为指定值的组合，"
为什么要这么奇怪的办法？
假设这50个数为a[0],a[1],......a[49]
那么这个5000001bytes的大表为:Table
0,0,......0;
1,1,1,1,....1;
2,2,2,.....2;
.......;
49,49,.....49
a[0]＋1个0 a[1]-a[0]个1 a[2]-a[1]个2 5000000-a[48]个49
这样一来，
n:=LeftCount;
while n>=0do
//寻找最高的起点
begin
if A[n]>LeftSum then
Dec
else
break;
end;
可以改成：
if LeftSum<a[LeftCount]
then
n=Table[LeftSum]
else
N=LeftCount;
当然要初始化那个大的Table，但只需要初始化一次，
那么效率......[]
2."很奇怪——我在家里的机器上（配置：毒龙1800+,256M DDR333）进行50个数的组合计算
——没有一次用时超过5秒的，全部都得到了理论最接近值。回到单位以后，用P4 1.6A，速
度慢了不说，经常还不能在20秒之内穷举完毕..."
P4的分支预测用得比较多，可能在这个时候，它的预测老是失败，然后导致效率的地下......[]
还有，那些子函数调用指令，在我的MMX200(小声点)上面，执行起来就很慢，在K6-2-450上很快的，
好像新型cpu对子程序调用有优化，不晓得是不是AMD的比Intel的好。可以尝试换成非递归的算法试一下。
3."天地良心呀！我也觉得那个帖子张兄结贴的时间早了些"
张剑波斑竹怎么会某名奇妙的节我的帖子???
5555555......
肯定有明堂.[]

晕倒！——刚才计算了半天，居然没看出来这个简单的事实：可能的结果数量仅仅与元素
总数有关：有N个元素就有 2^N-1 个和值（除去了一个元素都不取的情况），而与分组数量
没有关系。
我认为，如果基础思路不变，我的算法就只剩下一个地方可以优化了——尽可能的避免重
复性的和值计算。在DarwinZhang兄的话语中，我发现了影响我的算法速度的主要因素：由
于我的算法没有对数据进行“预处理”（也就是分组求和），不可避免的会进行大量的重复
性求和（即在某次计算中计算了A+B+C，在后来的计算中又计算了A+C+D——"A+C"被计算了
一次以上）。而一旦将算法改成基于“预处理”之后的和值数据，就会极大程度的减少“重
复求和”的发生（但是不可能完全去除——因为预处理只能杜绝分组内部的重复求和，而不
能避免分组之间的重复求和）——算法效率的提高显然与分组内部的可能和数量成正比。因
此，为了尽可能高的提高算法效率，我们应该在内存允许的情况下尽可能增加单个分组内的
元素个数。让我们计算一下...
假设内存用量控制在100M以内，如果结果为Integer类型——4Byte，那么总的组和数应该
小于100/4=25M。我们可以将50个元素分成（20,20,10）3组，那么，各组中元素的可能和分
别为（2^20,2^20,2^10），总计约2.1E+6个，似乎还有较大裕量。Wait!——仅仅保留和值
是不够的，我们必须知道某个给定的和值是由集合中的哪些元素计算出来的。为此，我们要
增加一个Bit数组来表示某个和使用了集合中的哪些元素，这个数组嘛，20位就够了，我们
完全可以用一个整型数来保存它。——好了，这个分组方案需要约 2.1M*(4+4)=16.8M 的内
存空间。
至于算法的速度提升嘛...——且听下回（下下回？）分解

——昨天晚上没贴上来，今天补贴

to creation-zy兄：
您认为效率的低下在于求和吗？
我看不是这样的，求一次和仅仅需要一次的CPU周期，呵呵。
那么你的判断也要一次cpu周期，那么......[]
也许我没有太明白您的意思，再看。

to DarwinZhang兄：
极大避免重复求和只是改进后的一个表现，还有一个随之而来的好处我昨天没有想到——
将算法的递归深度从50层减少到了3层！由于递归层数的大幅度减少，失败的试探必将随之
大幅度减少。如果我估计的不错的话，改进之后的算法中最耗时的部分不再是最后的递规，
而是前期的预处理——2*2^20+2^10次计算。为了提速，我们甚至可以考虑在预处理的求和
中也进行分组处理。

to creation-zy兄：
有个问题，就是您的一些预处理在递归的时候实际上是用不到的，
预处理所需要的时间和递归减少的时间上是不是真的能减少时间，
按我的经验来看，很可能会增加时间。

to DarwinZhang兄：
既然您这么说，只能靠“实践”了。
总算看明白您的思路了——非常有创意！
不过...请注意：
>>数据类型为decimal,范围从0到50000,小数点后保留两位。指定一个数值，程序从数组中
>>筛选出一部分数,使其和与指定的数值最接近，但不大于此数
呵呵，您没有注意到楼主并没有限制“指定一个数值”的大小范围，即换成整数之后的目
标和不一定在0到5000000的范围内的，因此5M很有可能是摆不平的。我试验时的目标和值为
123456789。我试验了一下，如果将和值改成小于等于5000000的数，我的算法肯定可以在50
毫秒之内得到最优值的

to creation-zy兄：
看来您了解得还不够准确啊 ！
if LeftSum<a[LeftCount] //假如比较大那么就直接用
then
n=Table[LeftSum]
else
N=LeftCount
这样，只要每个元素小于5000000就不会有问题，
和值只要在有符号整数范围内就可以了。[]

另外，您的这句话也不是很恰当：
"如果将和值改成小于等于5000000的数，我的算法肯定可以在50毫秒之内得到最优值的。"
因为我敢肯定您的随机算法是均匀分布的，但是，假如不是均匀分布，比如
绝大部分生成的随机数是在 1000~100000之间，而要求的和为 4000000，您实验一下看。[]
原因在于我上面对算法的分析：
“这个条件在随机数非常接近的时候将产生非常可怕的结果，(这时候K变得非常小)
即约束条件几乎无效（而且还增加了一点开销）。”

我试验了一下，将最大值改成了100000，N仍然为50，MaxSum为4000000——50个数全部加
起来都不到4000000...于是我将最大值改成了200000，95%的情况下16ms以内搞定，100%在
50ms内搞定。
——上面的实验能不能说明什么问题呢？

还有一个问题，我们以前一直都忽略了——如果使用大数组并进行随机访问，CPU将进行
内存与L2 Cache之间的数据交换，而这是受限于系统总线的（我做了一下实验，随机访问16
M的数组比随机访问16K的数组慢3-5倍）。如果使用我原来的算法，由于数据量非常小，完
全在L2 Cache中运算是没有问题的。如果采用我改进后的算法，虽然数组的数据量同样达到
了M级，但由于遍历是顺序的，主存与L2 Cache之间的数据交换频率不会太高。而您的算法
中的“Table[LeftSum]”中的LeftSum不是顺序的，属于随机访问。因此，查表定位法和我
的顺序比较法的效率熟高熟低还是未知数。

to creation-zy兄：
1."于是我将最大值改成了200000，95%的情况下16ms以内搞定，100%在50ms内搞定。
——上面的实验能不能说明什么问题呢？"
您其实应该改成90000~100000才好一点。[]
您似乎在怀疑我的算法分析的结论，我现在发现我确实犯了一点小错，但问题好像不大。[]
2."主存与L2 Cache之间的数据交换频率不会太高"
嗯，我的机器上面的倍频比较小，所以没有感觉，
现在的主流机器CPU和内存的速度差别好像很大了，倒是我忽略了。[]
通过算法分析，我发现您的While其实可以和For循环放在一起，我把我的程序写出来，
因为在网吧写的，所以可能有些小错误。程序如下：
const
Num = 200;
//200个元素
MinValue = 0;
MaxValue = 5000000;
//最大50000
Sum = 123456789;
//最终结果
var
LastRemain : Integer;
//保存当前的最小差值
A : Array [0..Num-1] of Integer;
//元素
Valid, //当前可用元素
Final : Array [0..Num-1] of Boolean;
//最终结果
procedure QuickSort(Lo,Hi:Integer);
//对初始元素排序
var
mid,temp,
H,L:Integer;
begin
H:=Hi;
L:=Lo;
mid:=(A[H]+A[L]) div 2;
repeat
while A[L]<middo
Inc(L);
while A[H]>middo
Dec(H);
if L<=H then

begin
temp:=A[L];
A[L]:=A[H];
A[H]:=temp;
Inc(L);
Dec(H);
end;
until L>H;
if H>Lo then
QuickSort(Lo,H);
if L<Hi then
QuickSort(L,Hi);
end;

procedur ReplaceResult(NewRemain:Integer);
//保存当前的最优组
begin
if LastRemain<=NewRemain then
exit;
MoveMemory(@Final[0],@Valid[0],Num);
LastRemain:=NewRemain;
end;

procedure FindSerial(EndPos,Remain:Integer);
var
i, //循环变量
sub : Integer;
//差值
begin
for i:=EndPosdo
wn to 0do
begin
sub:=Remain-A;
if Sub>=0
then
begin
//可以加入该元素
Valid:=True;
if (Sub>0)
then
begin
//没有到最理想的情况
if i>0
then
FindSerial(i-1,sub) //继续向下
else
ReplaceResult(sub);
//尝试加入解
end
else
begin
//到达最理想的情况
ReplaceResult(0);
Abort;
//退出递归循环
end;
Valie:=False;
end else
ReplaceResult(Remain);
//不能加入该元素,尝试加入解
end;
end;

procedure Init;
//初始化
var
i:Integer;
begin
FillChar(Valid,SizeOf(Valid),0);
//都未用标志
Randomize;
for i:=0 to Num-1do
//初始化元素值
A:=MinValue+Randomize(MaxValue-MinValue+1);

//最初剩余值为最大可能值
LastRemain:=Sum;
end;

procedure TForm1.WriteResult;
//写出结果
var
s:String;
i,total:Integer;
begin
s:='';
total:=0;
for i:=0 to Num-1do
if Final then

begin
s:=s+IntToStr(A)+#9;
total:=total+A;
end;
Memo1.Text:=S+'Total: '+IntToStr(Total);
end;

procedure TForm1.Button1Click;
var
i:Integer;
bt,etWord;
begin
bt:=GetTickCount;
Init;
QuickSort(0,Num-1);
try
FindSerial(Num-1,Sum);
except
end;
WriteResult;
et:=GetTickCount;
ShowMessage(IntToStr(et-bt));
end;

如有谬误，还请creation-zy兄指正！[]

to creation-zy 兄：
我又去试验了一下，才发现您这里的问题所在。
原来，在您那里的很多情况下，最优解并非是一个，而是有相当多个的！[]
假如有100个元素，那么他们的和大约有 2^100种和，
假设比较均匀的分布在 A[0]+A[1]+....+A[99]到0 上，而A是服从均匀分布，
那么这个区间大约是 5000000*50=2.5E8，（实际上和大约是服从高斯分布（1.25E8,?））
这和2^100约 1E30比是一个小得多得数字，那么等于所求数字的解就大约有1E23种之多！
也就是说，大约只尝试 几百到几千万次就可以得到最优化解了！
那么所求得值不在这个区间时，这时候最优解得数目很少了，
就需要穷举很多次才能求得解了。这才是耗时巨大的根本原因。
而我上面所讲的是几乎不存在等于所求数字的解的情况。[]
btw:
唉，上面的代码一堆的零星错误，我懒得改了。调入调试的时候哪位帮我改改，谢谢！