大家来看看如何能实现这个算法.

Question

得到有一堆的数字.用一个算法将这些数字组合起来(就是加起来)成最接近一个数(比如1000),求最优的一个组合.
比如有300\200\150\250\350四个数字,要组合成最接近500的数就是,300+200;150+350(越接近的越优先),250.这个算法我研究了很长时间,一直没有好的办法(我对算法很菜的).可能要经过多次循环扫描.那样代码可能会很长,效率又低.大家如果有好的主意还希望指教.谢谢了.

Answer 1

例如组成s=500
数组为a1=300，a2=200，a3=150，a4=250，a5=350
temp=s-a1
找余下的数中与temp最接近的
然后temp=s-a2
........
继续

Answer 2

我的意思是用动态规划来做：
先对a数组进行从大到小排序，f置空。
for i:=1 to maxa do begin
  if a[i]<= n then f[i].data:=a[i] else f[i].data:=0;
  maxf:=f[i].data;
  for j:=1 to i-1 do
    if (f[j].data+a[i]<=n)and(f[j].data+a[i]>maxf) then begin
      maxf:=f[j].data+a[i];
      maxid:=j;
    end;
  f[i].data:=maxf;
  f[i].pre:=maxid;
end;
似乎这样之后，对f进行一下遍历就可以找出最大的了。
没论证过无后效性，可能代码完全错误。