B Boblee Unregistered / Unconfirmed GUEST, unregistred user! 2006-04-12 #1 要求： 有n个实数，a1.....an，给定一个值P，给出一个高效的算法，使得从n个数中找到一组元素(an....am)，使元素之和最逼近值P。其中，一个元素也算，元素不能重复用。
有 有畏 Unregistered / Unconfirmed GUEST, unregistred user! 2006-04-12 #2 这个实际上是一个组合问题。 假设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) 次！
这个实际上是一个组合问题。 假设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) 次！
有 有畏 Unregistered / Unconfirmed GUEST, unregistred user! 2006-04-12 #3 上述算法是没有优化的。如果事先对a1.....an从小到大进行排序，就可以在获取组合的过程中把算法进行优化。比如，假如m个数的组合的和都比P大，就可以不对个数多于m的组合进行计算了；假如n个数的前m个数的和大于P，就可以不对包含后面的数的m个数的组合进行计算了。
上述算法是没有优化的。如果事先对a1.....an从小到大进行排序，就可以在获取组合的过程中把算法进行优化。比如，假如m个数的组合的和都比P大，就可以不对个数多于m的组合进行计算了；假如n个数的前m个数的和大于P，就可以不对包含后面的数的m个数的组合进行计算了。
C creation-zy Unregistered / Unconfirmed GUEST, unregistred user! 2006-04-14 #4 完全一样的问题，请看: http://www.delphibbs.com/delphibbs/dispq.asp?lid=1016791
