读书人

请问一个组合算法多谢

发布时间: 2013-01-07 10:02:24 作者: rapoo

请教一个组合算法,谢谢!
我有一组数据,两个列:【列1】,【列2】
其中【列1】的值是唯一的;【列2】的值都是小于1至49的数字

这组数据大概有40条左右
我想求个算法,将所有【列2】值相加后的值为50的组合都列出来,不知道可不可行,计算量是不是非常巨大???

特别说明:如果出现特殊情况,比如列2的值都大于25了,就拆分。

请大家给个思路,当然有delphi的算法代码做为测试更好,谢谢!

如果分不够,可以说一声,我加就是了。
[解决办法]
var
intsA: array of Integer; //保存列2
strsA: array of string; //保存列1
sList: TStringList;
arrayLength: Integer;
i, j: Integer;
begin
arrayLength := 50; //列的长度
SetLength(intsA, arrayLength); //初始化数组
SetLength(strsA, arrayLength); //初始化数组

//初始化数组的值
for i := 0 to arrayLength do
begin
intsA[i] := 1;
strsA[i] := 'aaaa';
end;
sList := TStringList.Create;
try
for i := 0 to arrayLength - 2 do
begin
for j := 1 to arrayLength - 1 do
begin
if intsA[i] + intsA[j] = 50 then //如果为50,保存列1的值
sList.Add(strsA[i] + '
[解决办法]
' + strsA[j])
end;
end;

//看一下有哪些值保存了
for i := 0 to sList.Count - 1 do
ShowMessage(sList[i]);
finally
sList.Free;
end;

end;
[解决办法]
新建工程、分别拖Tmemo和TButton各一个到窗体、点击Button1后,将下列代码覆盖你的unit1:

nit Unit1;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, ComCtrls, StdCtrls;

type
TForm1 = class(TForm)
Button1: TButton;
Memo1: TMemo;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;

implementation

{$R *.dfm}
type
TComputingData = record//存放数据
ID : string;//id编号
v : integer;//值
select : boolean;//是否被组合了
end;
TUpshotData = record//存放结果
ID:string;
v:string;
end;

var tmp:array[0..49]of TComputingData;//存放数据

procedure TForm1.Button1Click(Sender: TObject);
var i,len:integer;
upshot:array of TUpshotData;//存放结果
bID,bV:string;
function GetMatch(var idstr,vstr:string; v,index:integer):boolean;


var j:integer;
aID,aV:string;
begin
Result := false;//先假定没匹配
for j:=index to 49 do begin
if tmp[j].select then continue;
if v+tmp[j].v = 50 then begin //匹配上了
tmp[j].select:=true;
idstr:=idstr+','+Format('%.2d',[j]);
vstr:=vstr+','+inttostr(tmp[j].v);
Result := true;
exit;//不再找
end;
end;
//未匹配:
for j:=index to 49 do begin //将上一个数与当前数(和少于50)继续匹配下一个数
if tmp[j].select then continue;
if v+tmp[j].v>50 then continue;
aID:=idstr+','+Format('%.2d',[j]);
aV:=vstr+','+inttostr(tmp[j].v);
tmp[j].select:=true;
if GetMatch(aID,aV,v+tmp[j].v,j+1) then begin//匹配上了
idstr:=aID;
vstr:=aV;
Result := true;
break;//不再找
end
else
tmp[j].select:=false;
end;
end;
begin
memo1.Text:='';
randomize;
for i:=0 to 49 do begin
tmp[i].ID:=Format('%.2d',[i]);
tmp[i].v:=random(49)+1;
tmp[i].select:=false;
end;
memo1.Lines.Append('待处理数据:');
for i:=0 to 49 do
memo1.Lines.Append(Format('%.2d',[i])+'----'+inttostr(tmp[i].v));
len:=-1;
for i:=0 to 48 do begin
if tmp[i].select then continue;
bID:=Format('%.2d',[i]);
bV:=inttostr(tmp[i].v);
tmp[i].select:=true;
if GetMatch(bID,bV,tmp[i].v,i+1) then begin
inc(len);
setlength(upshot,len+1);
upshot[len].ID:=bID;
upshot[len].v:=bV;
end
else
tmp[i].select:=false;
end;
if len<0 then
memo1.Lines.Append('没有能组合为50的结果。')
else begin
memo1.Lines.Append('找到的组合结果是:');
for i:=0 to len do
memo1.Lines.Append('ID号:'+upshot[i].ID+'---对应的值:'+upshot[i].v);
end;
end;

end.

读书人网 >.NET

热点推荐