征求一个求和算法(200分)

  • 主题发起人 主题发起人 Boblee
  • 开始时间 开始时间
B

Boblee

Unregistered / Unconfirmed
GUEST, unregistred user!
要求:
有n个实数,a1.....an,给定一个值P,给出一个高效的算法,使得从n个数中找到一组元素(an....am),使元素之和最逼近值P。其中,一个元素也算,元素不能重复用。
 
这个实际上是一个组合问题。
假设SUMx是(a1,....,an)的x个数的组合的各个数之和,其中 1 <= x <= n; Delta是一个整数;Pt是一个有n个元素的数组,用来指示和最逼近P的x个数的组合的各个数。那么:
Delta = P;
Pt1 := -1;
Pt2 := -1;
.........
ptn ;= -1;
repeat
if ABS(SUMx -P) < Delta then
begin
Delta := ABS(SUMx -P);
设置Pt的1到x个元数为当前组合的各个元素;
end;
until 组合用完;
//总共需要循环 C(n,1) + C(n,2) + ...... + C(n,n) 次!
 
上述算法是没有优化的。如果事先对a1.....an从小到大进行排序,就可以在获取组合的过程中把算法进行优化。比如,假如m个数的组合的和都比P大,就可以不对个数多于m的组合进行计算了;假如n个数的前m个数的和大于P,就可以不对包含后面的数的m个数的组合进行计算了。
 
完全一样的问题,请看: http://www.delphibbs.com/delphibbs/dispq.asp?lid=1016791
 
后退
顶部