我有这样一道题，大家一起探索一下吧。(有点难度哦）(100分)

程序自动生成一个数组，数据个数在20到50个（随机），数据类型为decimal,范围从0到50000,小数点后保留两位。指定一个数值，程序从数组中筛选出一部分数,使其和与指定的数值最接近，但不大于此数，筛选过程写成一个函数。

请换行！

什么叫最接近的一部分数，到底要一个还是几个？？

难吗？
是否有时间或空间的要求
遍历一下就可以了
》筛选出一部分数
可以用败者树/胜者树
请参考数据结构
简单的就用O(n*m)的时间复杂度

你的问题可以简化为：在包含若干个非负整数的集合中，选出和值最接近指定数的几个数字。
（两位小数*100=>整数）

我写了一个算法，还没有优化，计算16个数字的时候已经要大约10秒左右的时间。20－50个数字
的时间根本无法接受。
IdealSum:3456789
897792 840756 389648 402370 546792 620474 734302 218257 400851 321503 181193 101873 766850
401822 388135 931868
Number Count: 16
766850 840756 897792 931868
3437266
388135 389648 840756 897792 931868
3448199
101873 388135 402370 734302 897792 931868
3456340
101873 181193 321503 401822 620474 897792 931868
3456525
101873 181193 218257 321503 401822 402370 897792 931868
3456678
181193 400851 401822 734302 840756 897792
3456716
MaxSum: 3456716

优化中...

Kao! 就改了一个Byte，时间复杂度就从O(N!)降低到接近O(N^2)。
type
IA=array of Integer;
function GenRandArray(MinNum,MaxNum,MinValue,MaxValue:Integer):IA;
var
i,n:Integer;
begin
Randomize;
n:=MinNum+Random(MaxNum-MinNum+1);
SetLength(Result,n);
for i:=0 to n-1do
Result:=MinValue+Random(MaxValue-MinValue+1);
end;
function FindMaxSum(A:IA;Sum:Integer):Integer;
var
MinLeft:Integer;
Used:array of Boolean;
procedure QuickSortIA(L, R: Integer);
//从小到大排序
var
I, J, P, M: Integer;
begin
repeat
I := L;
J := R;
P := (L + R) shr 1;
repeat
while A<A[P]do
Inc(I);
while A[J]>A[P]do
Dec(J);
if I <= J then
begin
M:=A;
A:=A[J];
A[J]:=M;
if P = I then
P := J
else
if P = J then
P := I;
Inc(I);
Dec(J);
end;
until I > J;
if L < J then
QuickSortIA(L, J);
L := I;
until I >= R;
end;
procedure FindLeft(LeftSum,LeftCount:Integer);
var
i,n,s:Integer;
Str:String;
begin
if (A[0]>LeftSum) or Used[0] then
begin
if LeftSum<MinLeft then
begin
MinLeft:=LeftSum;
Str:='';
s:=0;
n:=0;
for i:=0 to High(A)do
if Used then
begin
Str:=Str+IntToStr(A)+' ';
Inc(s,A);
Inc;
end;
Str:=Str+#13#10+IntToStr(s);
Form1.Memo1.Lines.Add(Str);
Application.ProcessMessages;
//如果已经达到理想和值，或者已经耗尽了所有元素——该结束了
if (LeftSum=0) or (n>=High(A)) then
Abort;
//产生哑异常，让try..except捕获——最方便的跳出递归的方法
end;
exit;
end;
n:=LeftCount;
while n>=0do
//寻找最高的起点
begin
if A[n]>LeftSum then
Dec
else
break;
end;
for i:=ndo
wnto 0do
//贪心算法——先大后小
begin
Used:=true;
FindLeft(LeftSum-A,i-1);
//确保以后取的值比现在小
Used:=false;
end;
end;
begin
QuickSortIA(0,High(A));
SetLength(Used,High(A)+1);
FillChar(Used[0],(High(A)+1)*SizeOf(Boolean),0);
MinLeft:=Sum;
try
FindLeft(Sum,High(A));
except
end;
Result:=Sum-MinLeft;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
A:IA;
i:Integer;
Str:String;
begin
A:=GenRandArray(SpinEdit1.Value,SpinEdit2.Value,0,1000000);
//Gen..ay(20,20,0,1000000);
Str:='';
for i:=0 to High(A)do
Str:=Str+IntToStr(A)+' ';
Memo1.Text:='IdealSum: '+Edit1.Text;
//3456789
Memo1.Lines.Add(Str+#13#10'Number Count: '+IntToStr(High(A)+1)+#13#10);
Memo1.Lines.Add(#13#10'MaxSum: '+IntToStr(FindMaxSum(A,StrToInt(Edit1.Text))));
end;

现在运行起来就爽多了——毫秒级搞定！
IdealSum: 3456789
172256 364819 732060 41802 465300 742102 99686 890487 783935 823647 510794 770556 345017
623186 431258 747470 906273 831441 575187 444265
Number Count: 20
823647 831441 890487 906273
3451848
41802 783935 831441 890487 906273
3453938
41802 99686 732060 783935 890487 906273
3454243
364819 510794 783935 890487 906273
3456308
99686 345017 431258 783935 890487 906273
3456656
41802 99686 172256 364819 465300 575187 831441 906273
3456764
41802 99686 345017 364819 431258 444265 823647 906273
3456767
345017 431258 444265 575187 770556 890487
3456770
MaxSum: 3456770
OK？

这是典型的DP(动态规划问题）

creation-zy大虾,为要何如此复杂?
我写了一个程序不知道对不对题意,请指教!
type
TSubData= Record
Pos:Integer;
SubValue:Integer;
end;
TSubArrayData = Array of TSubData;
procedure QuickSort(A:TSubArrayData;L,H:Integer);
var
Lo,Hi,Mid: Integer;
Temp:TSubData;
begin
Lo:=L;
Hi:=H;
Mid := A[(Lo + Hi) div 2].SubValue;
repeat
while A[Lo].SubValue > Middo
Inc(Lo);
while A[Hi].SubValue < Middo
Dec(Hi);
if Lo <= Hi then
begin
Temp := A[Lo];
A[Lo] := A[Hi];
A[Hi] := Temp;
Inc(Lo);
Dec(Hi);
end;
until Lo > Hi;
if Hi > L then
QuickSort(A, L, Hi);
if Lo < H then
QuickSort(A, Lo, H);
end;

procedure TForm1.Button1Click(Sender: TObject);
var
RanArray:Array of Integer;
SubArray:TSubArrayData;
Len,i,Num:Integer;
begin
Randomize;
Len:=Random(50-30+1)+30;
SetLength(RanArray,Len);
Num:=StrToInt(Edit1.Text);
Memo1.Clear;
Memo1.Lines.Add('Numbers:');
for i:=0 to Len-1do
begin
RanArray:=Random(50000*100);
Memo1.Lines.Add(IntToStr(RanArray));
if RanArray-Num<=0 then
begin
//选非负数
SetLength(SubArray,Length(SubArray)+1);
SubArray[High(SubArray)].SubValue:=RanArray-Num;
SubArray[High(SubArray)].Pos:=i;
end;
end;
QuickSort(SubArray,0,High(SubArray));//排序,如果只找最接近的就直接找到最大值
if Length(SubArray)>0
then
Memo1.Lines.Add('Closest Value is:'+
IntToStr(SubArray[0].Pos)+':'
+IntToStr(RanArray[SubArray[0].Pos]))
else
Memo1.Lines.Add('Can''t find!');
end;

gz

to DarwinZhang:
恕我眼拙，在您的程序中我没有发现对集合中的元素进行相加的代码。如果我没有理解错的话，
您的算法好像是从一组数字中找到不大于给定值的最大的数，而这和gzygf要求的“指定一个数值，
程序从数组中筛选出一部分数,使其和与指定的数值最接近，但不大于此数”完全不一样。
~~~~~~~~~~~~~~~~~！~~~~~~~~~~~~~~~~~~
除此之外，单纯看您的算法，还有很大的问题——为了从一组符合要求的数字中找到一个最大值，
并不需要进行Quick排序，这样效率很低，最快的方法应该是冒泡排序——只找到最大的一个即可。
MaxValue:=-1;
MaxPos:=-1;
for ...
...
if RanArray-Num<=0 then
//选非负数
begin
if RanArray>MaxValue then
begin
//就这么简单！
MaxValue:=RanArray;
MaxPos:=i;
end;
end;
...
...
if MaxPos>=0 then
Memo1.Lines.Add(Format("Value:%d Pos:%d",[MaxValue,MaxPos]))
else
Memo1.Lines.Add('Can''t find!');
ok?

to creation-zy大侠:
我的理解是找到比指定的数字小一点的一些(不是一个)数字,
我后来仔细的看了一下题目(长,太难看了)
才知道是求若干数的和使这个和与指定的数接近,
你的贪心算法是可行的(虽然贪心算法不能最快的找到最优组合).
我现在也写不出比creation-zy大侠更简单的代码.
谢谢你的回答!

to creation-zy:
复习一下数据结构的书，才发现你的算法不是什么贪心算法，是个回溯法嘛。另外，
有序表的查找用折半法可比顺序法快得多。不过，这在你的程序中根本不起作用，因为
快速排序法的时间消耗得最多。其实根本就不要排序，直接查找的速度会快得多。
只要定义一个数组保存数据就好了。

概念不能混淆！不是什么名称的问题。不能以为先来个大的就是贪心算法了。
显然，他只要求找到一个就可以了，而不必每个遍历，这样就不必排序了。
显然，择半法比你的顺序查找快得多，而且，
写一个快得多的算法并不复杂,不过看你是斑竹，就
以后懒得来了.

非常抱歉，本人措辞不当，还望同道海涵。
本来想看看更好的算法的，现在却...
我的意思是：
他要求获得“最接近的和”，我就不断通过回溯进行逼近。
我主要是不明白您提到的“查找”如何使用？
比如：
在 12 18 24 31 中求与 50 最接近的和（小于等于50），应如何计算？如何查找？
( 另：算法面前，人人平等，没有什么版主不版主的区别 )

找了好一阵，终于找到了效率不高的代码：
n:=LeftCount;
while n>=0do
//寻找最高的起点
begin
if A[n]>LeftSum then
Dec
else
break;
end;

如果在此处改用折半查找，无疑会降低算法的总体时间复杂度。但是，我认为这样做带来的
效率提升不会有多明显——我的目的是在一个升序序列中，从后往前找到比指定值小的第一个
数。采用while循环是最笨但最直接的方法，虽然它的时间复杂度与LeftCount相当，但是每一步
的操作非常简单——判断一个数、递减、比较；比较而言，如果采用折半法，时间复杂度将
降低到Log2(LeftCount)，但它的每一步都要进行两个数的比较——A[n]要小于等于LeftSum，
并且A[n+1]要大于LeftSum，只有这样才能满足“第一个小于”的要求，除此之外，为了实现
“折半”，还要进行额外的运算。因此，可以认为折半法每一步花费的时间相当于前者的2倍。
另外，对本问题来说，N在20到50之间，一般情况下可以取36作为平均。由于本问题的特殊性，
LeftCount的统计分布必然是从0到N单调递减的，并且基本上是以几何级数递减（因为每个大的
LeftCount将递归调用若干个较小的LeftCount过程——除非遇到A[0]>LeftSum的情况）——越
靠近0的LeftCount出现的概率越大。为了证实我的估计，我进行了统计：
...
n:=LeftCount;
{$IFDEF CountLeftSum}
Inc(LSCount[n]);
//统计数组
{$ENDIF}
while ...
结果如下：
0: 60636 //注意，0..7呈等比下降数列
1: 30390
2: 15094
3: 7765
4: 4578
5: 2827
6: 1648
7: 1113
8: 730
9: 432
10: 299
11: 153
12: 103
13: 48
14: 45
15: 44
16: 42
17: 40
18: 38
19: 35
20: 33
21: 29
22: 26
23: 22
24: 19
25: 15
26: 5
27: 4
28: 3
29: 3
30: 3
31: 3
32: 2
33: 1
34: 1
35: 2
——哈哈！比我想象的还要理想！完全可以认为，平均说来，LeftCount为1左右（大于5的
情况完全可以忽略）！！！在这样的条件之下，折半法根本毫无优势可言，甚至很可能用更
长的时间！
看来，我采用的“笨办法”是极为高效的。 )
我认为，除非在算法的系统框架上进行改进，否则就不会有太大的速度提升。

还是那句话
用 败者数

接受答案了.