求一算法：在m个整数中，求n个数的组合，若这n个数的和等于sum，则将这n个数打印出来。（m,n均不定，1<=n<=m,m个数的值,sum的值由界面输入.)
看起来好像很简单,实际写起来好像还有点复杂,希望各位提供算法和代码,(兼顾一下算法的效率,若m的值比较大,怎么办?总不至于在机器面前等上几十分钟吧?m的值小于100,平常一般在20左右.)不胜感激!!!!!
看起来好像很简单,实际写起来好像还有点复杂,希望各位提供算法和代码,(兼顾一下算法的效率,若m的值比较大,怎么办?总不至于在机器面前等上几十分钟吧?m的值小于100,平常一般在20左右.)不胜感激!!!!!
还是只要一组下面可得到一个组合
unit Unit1;interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;type
TForm1 = class(TForm)
Button1: TButton;
Memo1: TMemo;
Edit1: TEdit;
procedure FormCreate(Sender: TObject);
procedure Sum(a: array of Integer; x: Integer);
procedure Button1Click(Sender: TObject);
function knap(S, n: Integer): Integer;
private
{ Private declarations }
public
{ Public declarations }
end;var
Form1: TForm1;
a: array [0..25] of Integer;
implementation{$R *.dfm}procedure TForm1.FormCreate(Sender: TObject);
var
i: Integer;
begin
for i := 0 to 25 do
begin
Randomize();
a[i] := Abs(Random(50));
end;
end;procedure TForm1.Sum(a: array of Integer; x: Integer);
var
i,j,temp: Integer;
begin
if ( knap(50,i) > 0 )then Memo1.Lines.Add( 'OK')
else continue;end;procedure TForm1.Button1Click(Sender: TObject);
var
i,j,temp: Integer;
begin
for i := Low(a) to High(a) -1 do
for j:= i+1 to High(a) do
begin
if a[i] > a[j] then
begin
temp := a[i];
a[i] := a[j];
a[j] := temp;
end;
end;
Sum(a, 50);
end;function TForm1.knap(S, n: Integer): Integer;
begin
if(S = 0) then
begin
result := 1;
exit;
end; if ( (s< 0)or ( (s>0) and (n < 1) )) then
begin
result := 0;
exit;
end; if (knap(s-a[n], n-1) > 0) then
begin
Memo1.Lines.Add(IntToStr(a[n]));
result := 1;
exit;
end;
Result := knap(s,n-1);
end;end.
所有可能的组合.谢谢你!
to AirFish(铁甲飞鱼) ( ) 信誉：93当你有这个需求的时候,你就不会这么叫了.
所有可能的组合.
能给出所有组合的代码吗？
万分谢你！！!
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls,DateUtils;const MAXLEN=26;type
TForm1 = class(TForm)
Button1: TButton;
Memo1: TMemo;
Edit1: TEdit;
Button2: TButton;
Label1: TLabel;
Label2: TLabel;
Memo2: TMemo;
Edit2: TEdit;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
answers:TStringList;
sum:integer;
data:array[1..MAXLEN] of integer;
answer: array[1..MAXLEN] of boolean;
procedure SaveAnswer();
procedure Question(const ipos:integer;const tsum:integer);
public
{ Public declarations }
end;var
Form1: TForm1;procedure SortArray(var data: array of integer);implementation{$R *.dfm}
//初始化
procedure TForm1.Button1Click(Sender: TObject);
var
i:integer;
begin
Memo2.Lines.Clear;
Randomize;
sum:=integer(Random(200));
Edit1.Text:=inttostr(sum);
for i:=Low(data) to High(data) do
begin
answer[i]:=FALSE;
Randomize;
data[i]:=integer(Random(25))+1; //去除等于0的情况，可以优化速度。所以有0值时，应先去除0，算好后再把0项加上。
Memo2.Lines.Add(inttostr(data[i]));
end;
end;//排序
procedure SortArray(var data: array of integer);
var
i,j,k,temp:integer;
begin
for i:=Low(data) to High(data)-1 do
begin
k:=i;
for j:=k+1 to High(data) do
begin
if data[j]<data[k] then
k:=j;
end;
if k<>i then
begin
temp:=data[k];
data[k]:=data[i];
data[i]:=temp;
end;
end;
end;//存结果
procedure TForm1.SaveAnswer();
var
i:integer;
tempstr:string;
begin
tempstr:='';
for i:=Low(answer) to High(answer) do
if answer[i] then
// tempstr:=tempstr+inttostr(data[i])+' '; //此处耗时
answers.Add(tempstr); //此处耗时
end;//递归求值
procedure TForm1.Question(const ipos:integer;const tsum:integer);
begin
if ipos>High(data) then
exit;
if(data[ipos]=tsum) then
begin
answer[ipos]:=True;
SaveAnswer();
Question(ipos+1,0);
answer[ipos]:=false;
Question(ipos+1,tsum);
end
else if(data[ipos]<tsum) then
begin
answer[ipos]:=True;
Question(ipos+1,tsum-data[ipos]);
answer[ipos]:=false;
Question(ipos+1,tsum);
end
else
exit;
end;//main
procedure TForm1.Button2Click(Sender: TObject);
var
i,tsum:integer;
tstart,tend:TDateTime;
begin
tsum:=0;
Memo1.Lines.Clear;
Edit2.Text:='';
answers:=TStringList.Create;
for i:=Low(data) to High(data) do
tsum:=tsum+data[i];
if(tsum>=sum) then
begin
SortArray(data);
tstart:=time;
Question(Low(data),sum);
tend:=time;
end;
Edit2.Text:=inttostr(answers.Count);
//Memo1.Lines.AddStrings(answers); //此处耗时
showMessage(floattostr(MilliSecondsBetween(tend,tstart))+'ms');
answers.Free;
end;end.
能把你那高效的代码贴出来看看吗？牛皮可不是吹得哟，有...贴出瞧瞧。