高分征求一个算法：排列组合的算法？？？(200分)

Y

yuanyoufa

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-30

• #1

假如我有n条记录，内容如下：
ID shul
1 2
2 5
3 4
4 1

shul这个字段内容的随机的， 如过我的要求是把上面4（可能不止这四个记录）个记录数字排列先找两两累加或者三三累加，如果发现刚好等10就把那个ID保存下来，或者最接近10也可以保存ID，也就是寻求最接近10的组合（可以是1条记录也可以两个记录累加等10也可以是3个累加等于10或着。。。），反正是最优组合。

 

Y

yuanyoufa

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-30

• #2

各位大哥，如果分不够，我可以在加啊！！

 

D

d5love

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-31

• #3

在数据库里操作感觉很难呀,
而且太人性化了:到底是两两累还是三三累加 是相邻的相加,还是排列组合
等待高手把,
帮顶了

 

N

nicai_wgl

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-31

• #4

组合问题，草拟一个函数供参考
{ 阶乘函数 }
function factorial(Number: Integer): Integer;
var
i: Integer;
begin
if i < 1 then
begin
Result := 1;
exit;
end;
Result := Number;
i := Number - 1;
while i > 0 do
begin
Result := Result * i;
Dec(i);
end;
end;

const
RecordCount = 1000;
Target = 10;
var
RecordArray: array[1..RecordCount] of Integer;
ResultArray: array of Integer;
ResultCount: Integer;
i, j, k; Integer;
begin
{ 先从数据库读入记录 }
.....
{ 计算组合结果的数量 }
ResultCount := 0;
{ RecordCount阶乘 }
k := factorial(RecordCount);
for i := 1 to RecordCount do
begin
{ 组合公式 c(n,m)=p(n,m)/m!=n!/(m!*(n-m)!) }
Inc(ResultCount, k div (factorial(i) * factorial(RecordCount - i)));
end;
{ 设置结果数组长度 }
SetLength(ResultArray, ResultCount);
{ 组合结果写入结果数组 }
for i := 1 to RecordCount do
begin
...
end;
{ 对结果数组进行从小到大排列,得出结果 }
...
end;

 

N

nicai_wgl

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-31

• #5

{ 组合结果写入结果数组 }
...可能用递归比较好，有时间再写....

{ 对结果数组进行从小到大排列,得出结果 }
...还要解析出原来组合的ID号,有点复杂....

 

8

8525310

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-31

• #6

你这里的最优组合是只找到两两相加的等于10了，其余的就不用考虑了吗？？
给你一个建议。先取出一个ID号。保存这个ID号。然后，用这个ID号对应的shul
和其他的数据两两相加，如果，等于10，保存ID。不等于10。保存到数组里。查完这个ID后。屏蔽掉这个ID，考虑其他两两相加的情况。。两两相加考虑完了，在以同样的方法考虑33相加///

 

D

dey-999

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-31

• #7

你需要确定相加的时候ID号是否连续,连续的话用个函数然后用SQL调用也就可以了,否则最好是参考楼上的

 

S

strongburn

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-31

• #8

两个数组合的情况
第一步：建立数组且用表中的数据初始化。假设数组为SourceArray :array [0..RecordCount-1] of Integer;
第二步：建立存放信息表。字段为 "第一个数"，“第二个数”，“结果”。假设表为table2.
第三步：建立循环。
for i:=1 to RecordCount do //对数据表进行循环
begin
for j:=i to RecordCount-1 do
begin
table2.append;
table2.fieldbyname('第一个数').asinteger:=table1.fieldbyname('shul').asinteger;
table2.fieldbyname('第二个数').asinteger:= SourceArray[j];
table2.fieldbyname('结果').asinteger:= SourceArray[j]+table1.fieldbyname('shul').asinteger;
table2.post;
end;
table1.next;
end;
第四步：对table2按结果进行排序。根据你想要的选择范围就好了。
大概是这个思路，如果是3个相加或4....可考虑动态创建数组，看看是否可以使用递归。

 

Y

yuanyoufa

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-31

• #9

谢谢楼上的各位指导，
可是现在有个问题就是现在不是一组数据来判断最优化组合，现在是几千条数据分组来判断最优化组合，比如：
ID 分组 shul 符合数据
1 A 2 10
2 A 5 10
3 A 4 10
4 A 1 10
5 B 3 6
6 B 2 6
7 B 3 6
8 C 7 8
9 D 2 5
10 D 4 5
.........
对于以上的A组 要挑出接近或等于10的最优化组合（ID为2和3和4能满足）。
对于B组， 要挑出接近或等于6的最优化组合（ID为5和7能满足）。
对于C组， 要挑出接近或等于8的最优化组合（ID为8刚好满足）。
对于D组， 要挑出接近或等于5的最优化组合（ID为10能满足）。
这样怎么实现？？

 

N

nicai_wgl

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-08-31

• #10

呵呵，再加一级循环喽，如果数据量大的话计算量还是很大的。

 

Y

yuanyoufa

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-09-01

• #11

to nicai_wgl,
能否在给点提示。期待中！

 

N

nicai_wgl

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-09-01

• #12

1、先把每个分组的记录找出来。
2、对每个分组的记录找出优化组合。
3、每个分组的记录找出化化组合的算法是一样的，不一样的是记录数和优化组合标准。
4、可以做一个通用函数，对每个分组均可使用。

 

N

nicai_wgl

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-09-01

• #13

参考函数
SrcList: 分组记录 DesList: 优化组合记录ID输出, Target:优化组合目标;
function combination(SrcList, DesList: TList; Target: Integer): Boolean;

 

N

nicai_wgl

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-09-01

• #14

想来想去，取最优组合还是只能把全部组合列出来，再排列取合适的。
例如 4.5.7.8.12.45.23.53.16 这些数中取出和为100的最优组合，我们可以判断的：
1、这些数组合的最小和为4，最大数为所有数全部相加的和。
2、如果目标值小于4或者大于最大数，则最优组合很简单，为4或全部数。
3、如果目标值在两者之间，就比较复杂了。
4、可以用逐步逼近目标值的算法，但是不一定是最优的，或者最优有几个组合只能取到一个。
5、把组合值全部列出再排列取值，不会遗漏但数据量大时计算量非常大。

 

Y

yuanyoufa

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-09-02

• #15

to nicai_wgl,
谢谢你的精彩回答，我先试试，不明白的在请教你！
谢谢你

 

网

网中戏

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-09-04

• #16

顶