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-1 do
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[I]<A[P] do Inc(I);
while A[J]>A[P] do Dec(J);
if I <= J then
begin
M:=A[I];
A[I]:=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(n);
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>=0 do //寻找最高的起点
begin
if A[n]>LeftSum then
Dec(n)
else
break;
end;
for i:=n downto 0 do //贪心算法——先大后小
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; |