[b]这道题真这么难吗？[/b]

在很久很久以前,我在工作中遇到类似的问题.
在做假帐的时候,我会遇到一个虚报的费用,
然后我需要在一大堆需要报销的收据里面,
挑出若干张费用收据,凑成那个虚报的费用,
以便填帐,如果实在找不到相等的结果,就拿最接近的结果进行涂改增补之类的.

我记得那时候,我还专门拿EXCEL来写了一个程序,现在找不到了,
我就大概说一下当初的想法,自己整理一下,程序就出来了:

1.排序,从大到小排
2.比目标值S大的加数,全部剔除
3.从大到小开始相加,N9+N8+N7....
4.如果等于目标值S,就有结果了.
5.如果比S小,继续加下一个数.
6.如果比S大,最后一个加数换下一个.假如这时候是N5,就把最后一个加数N5,换成N4....一直到N1
7.如果加到最后一个值N1,还是比S大,倒回倒数第二个加数往后类推.
8.直至第一个加数开始到最后一个加数之和,仍比S小,为止.例如:(N5+N4+....+N1<S)

9.至于最接近序列,可以在比较过程中保存差的绝对值最小的一组加数.

我把程序写出来之后,(这个代码我得等到明年再贴上来)
才发现一个问题:

表中的加数,最大的是五千多,最小是九百多,个数是173个,要的和是42万,
粗略估计了一下,需要一百多个加数.
我用VFP写出代码之后运行的时候,一直很疑惑怎么答案还不出来?
然后调试一下,前面一百多个加数一直没变化,循环还在后面的几十个数里面跳动.

然后我才想到,这个个数太多了,和与加数之间的差距太大了.
于是乎,我sum了一下,数据表中的总和是451649.22
居然跟42万差不远啊.哈哈,这下子问题变得简单了.
451649.22-420000=31649.22

只要找到加数的和接近31649.22
把这些加数排除后,剩下的加数和岂不是接近42万了?
答案马上就出来了.

5336.60+4928.81+4593.67+4583.25+4486.88+4355.22+3364.02=31648.45≈31649.22

[b]去这里看看，panpende老师的代码相当不错。[/b]
[url=http://bbs.bccn.net/thread-358216-2-1.html]http://bbs.bccn.net/thread-358216-2-1.html[/url]

呵呵,过不了年了.
以下方法都是用的普通遍历.

利用字符串:
USE K:\test.dbf
SORT TO K:\tes2.dbf ON A1 /D
USE K:\tes2.dbf
ss=420000
*ss=31649.22
r1=STR(1,10)
s1="0+"+STR(A1,10,2)
s3=s1
t2=ss
DO WHILE !EOF()
    t1=EVALUATE(s1)
    IF ABS(t1-ss)<t2 THEN 
        t2=ABS(t1-ss)
        s3=s1
    ENDIF 
    IF t1=ss THEN 
        ?STRTRAN(SUBSTR(s1,3)+"="+STR(ss,10,2)," ","")
        *EXIT 
    ENDIF 
    IF t1<ss AND VAL(RIGHT(r1,10))<RECCOUNT() THEN 
            r1=r1+RIGHT(r1,10)
            s1=s1+"+"+RIGHT(s1,10)
    ENDIF
        r2=VAL(RIGHT(r1,10))
        r1=LEFT(r1,LEN(r1)-10)
        s1=LEFT(s1,RAT("+",s1)-1)
        IF r2=RECCOUNT() THEN 
            r2=VAL(RIGHT(r1,10))
            r1=LEFT(r1,LEN(r1)-10)
            s1=LEFT(s1,RAT("+",s1)-1)
            IF "0"=s1 AND r2=RECCOUNT() THEN 
                EXIT
            ENDIF 
        ENDIF 
        GOTO r2+1
        r1=r1+STR(r2+1)
        s1=s1+"+"+STR(A1,10,2)
ENDDO
IF t2>0 THEN 
?STRTRAN(SUBSTR(s3,3)+"="+ALLTRIM(STR(EVALUATE(s3),10,2))+"≈"+ALLTRIM(STR(ss,10,2))," ","")
ENDIF 

利用数据表.
USE K:\test.dbf
SELECT *,000 as A3 FROM test ORDER BY 1 DESC INTO TABLE K:\tes3.dbf 
SELECT tes3
GOTO TOP 
replace A3 WITH -1
ss=420000
*ss=31649.22
s1=A1
r1=1
DO WHILE !(s1=ss)
    IF s1>ss THEN 
        r1=A3
        replace A3 WITH 0
        s1=s1-A1
    ENDIF 
    SKIP 
    DO WHILE EOF()
        GOTO r1
        r1=A3
        replace A3 WITH 0
        IF r1=-1 THEN 
            s1=ss
            EXIT
        ENDIF 
        s1=s1-A1
        GOTO r1
        r1=A3
        replace A3 WITH 0
        s1=s1-A1
        SKIP 
    ENDDO
    replace A3 WITH r1
    r1=RECNO()
    s1=s1+A1
ENDDO
SELECT A1 FROM tes3 WHERE A3<>0

数组比表更快:

USE K:\test.dbf
SELECT A1 FROM test ORDER BY 1 DESC INTO ARRAY Y1
N=_tally 
ss=420000
*ss=31649.22
DIMENSION r(N)
k=1
r(k)=1
s1=Y1(r(1))
DO WHILE !(s1=ss)
    IF s1>ss THEN 
        s1=s1-Y1(r(k))
        r(k)=r(k)+1
    ELSE
        k=k+1
        r(k)=r(k-1)+1
    ENDIF 
    DO WHILE r(K)>N
        IF k=1 THEN 
            s1=ss
            EXIT 
        ENDIF 
        k=k-1
        s1=s1-Y1(r(k))
        r(k)=r(k)+1
    ENDDO 
    s1=s1+Y1(r(k))
ENDDO

s2=STR(Y1(r(1)),10,2)
FOR i=2 TO k
    s2=s2+"+"+STR(Y1(r(i)),10,2)
NEXT 
s2=STRTRAN(s2+"="+STR(EVALUATE(s2),10,2)," ","")
?s2


最后一个是以递归方式调用,但最大嵌套数为126,这个题目超出了要求,不过可以以差为目标值:
*USE K:\test.dbf
SELECT A1 FROM test ORDER BY 1 DESC INTO ARRAY Y1
N=_tally 
ss=31649.22
s1=SUBSTR(Sums(1,ss),2)
?STRTRAN(s1+"="+STR(EVALUATE(s1),10,2)," ","")

FUNCTION Sums(k,s0)
LOCAL i,k,s0,s2
FOR i=k TO N
    DO CASE
    CASE Y1(i)=s0
        RETURN "+"+STR(Y1(i),10,2)
    CASE Y1(i)<s0
        s2=Sums(i+1,s0-Y1(i))
        IF ""<s2 THEN 
            RETURN "+"+STR(Y1(i),10,2)+s2
        ENDIF 
    ENDCASE
NEXT     
RETURN ""
ENDFUNC

再次修改:

USE test.dbf
N=RECCOUNT()
ss=420000
*ss=31649.22
COPY TO ARRAY Y1 FIELDS A1
=ASORT(Y1,1,-1,1)
DIMENSION r(N)
k=1
r(k)=1
s1=Y1(r(k))
DO WHILE !(s1=ss)
   IF s1>ss THEN 
      s1=s1-Y1(r(k))
      r(k)=r(k)+1
   ELSE
      k=k+1
      r(k)=r(k-1)+1
   ENDIF 
   DO WHILE r(k)>N
      IF k=1 THEN 
         return
      ENDIF 
      k=k-1
      s1=s1-Y1(r(k))
      r(k)=r(k)+1
   ENDDO 
   s1=s1+Y1(r(k))
ENDDO
   s2=STR(Y1(r(1)),10,2)
   FOR i=2 TO k
       s2=s2+"+"+STR(Y1(r(i)),10,2)
   NEXT 
?STRTRAN(s2+"="+STR(EVALUATE(s2),10,2)," ","")

比起来,速度有点慢,但也许是偶然因素,把目标值减少一个零,就比他的快.
我写的这些代码方法,理论上好像都是叫做"遍历"吧,我不太懂理论和数据.
好像应该还有更好更快的数据处理办法,但我的水平,也就到此为止了.

用了两个小时,得到了3245个结果,现在还没完......

moz老师谢谢你！你的回帖的代码相当不错，学习了。

算到三万多个结果的时候,我的电脑死掉了.

如果后面加多一个零,程序要出错了,应该要在前面加入目标值的限制 [和,最小值]