从一组数字中任意组合N个数字，使之和在某个数值范围

drunk

学习学习

lin0308

看看什么东西..

tnt844

回复一下看看，代码整理和精简确是要的。

yigao

正在考虑一个关于随机数的程序，这个例子可以参考一下

gapkiller

学习一下,偷窥...

supersp

对代码进行了修改，去除显示0的错误，前面已有算法就不再使用2个新数组，在原数组上操作，只是使用折半法查找105/2 的界限，当作2个数组用。
15个元素时，编译器内运行65-70ms，编译成exe后运行33-35ms，没什么变化
但是当元素成百上千时，比前面的代码效率提高很多。
另外，在数组内数字全部 >=58 时，只做了判断，但是没做处理。

#Include <Array.au3>


Dim $aArray[15] = [51, 8, 13, 2, 52, 61, 37, 85, 19, 11, 7, 62, 22, 38, 79]
$begin = TimerInit()
_ArraySort($aArray)
$m = UBound($aArray)
Global $display[1]
;折半法，找出 105/2 的分界线
Local $min=0,$max=$m-1,$mid,$fjx=-1
If $aArray[0]>=58 Then $fjx=0
If $aArray[$max]<58 Then $fjx=$max
While $fjx=-1
        $mid=($min+$max)/2
        If $aArray[$mid] >= 58 Then 
                $max=$mid-1
                If $aArray[$mid-1] < 58 Then $fjx=$mid
        Else
                $min=$mid+1
                If $aArray[$mid+1] >= 58 Then $fjx=$mid+1
        EndIf
WEnd

_xh(0,"",$fjx-1) 
For $v2 = $fjx To $m-1
        _xh($aArray[$v2],String($aArray[$v2])&"+",$fjx-1)
Next
_ArrayDelete($display, 0)
$dif = TimerDiff($begin)
_ArrayDisplay($display,"耗时:"&$dif)


Func _xh($var,$str,$n)
        For $i = $n To 0 Step -1
                $num = Execute("$var + $aArray[$i]")
                Switch $num
                        Case 105 To 1500
                                ContinueLoop
                        Case 102 To 105
                                _ArrayAdd($display,$str&String($aArray[$i])&"="&String($num))
                        Case 1 To 102
                                _xh($num,$str&String($aArray[$i]&"+"),$i-1)
                EndSwitch
        Next
EndFunc

C.L

回复 36# supersp

效率的确高，佩服，学习了。

xlcwxl

不知道怎么弄，这属于“智能”问题，我却是愚蠢的。
顽固不化 发表于 2010-1-20 10:01

你们都很谦虚

the886

看看...............................

tianya1631

这么多高手，学习了。。。。。。

afan

继续讨论下这个问题，如果我只需要得到任意一个匹配的结果，而不需要全部的组合，如何才能更加高效。
发现各位都使用了递归，如果获得一个结果后，递归仍未完，肯定会延迟，貌似跳出递归又不太好办……
我在一楼使用的方法很好办，将第二个for嵌入第一个for，匹配到第一个即ExitLoop 2 即可，但可恨的是_ArrayCombinations函数在组合集>20仍会报错（此例只有15，仍可正常）。请教各位有无好的办法~~

afan

回复 12# sanmoking


    新问题，如何不使用递归，改用循环？

afan

回复 36# supersp


    同问新问题，如何不使用递归，改用循环？

阿福

同问新问题，如何不使用递归，改用循环？
afan 发表于 2010-1-24 01:28

算法不是我的,我只在supersp的基础上改为非递归. 没对比,估计效率要比二分优化的递归低.
#Include <Array.au3>
Dim $aArray[35] = [51, 8, 13, 2, 52, 61, 37, 85, 19, 11, 7, 62, 22, 38, 79, 53,54,55,56,57,58,59,60,63,64,90,91,92,93,94,95,96,97,98,99 ]

$begin = TimerInit()
_ArraySort($aArray)
$m = UBound($aArray)
Global $display[1]
;折半法，找出 105/2 的分界线
Local $min=0,$max=$m-1,$mid,$fjx=-1
If $aArray[0]>=58 Then $fjx=0
If $aArray[$max]<58 Then $fjx=$max
While $fjx=-1
        $mid=($min+$max)/2
        If $aArray[$mid] >= 58 Then
                $max=$mid-1
                If $aArray[$mid-1] < 58 Then $fjx=$mid
        Else
                $min=$mid+1
                If $aArray[$mid+1] >= 58 Then $fjx=$mid+1
        EndIf
WEnd

_xh(0,"",$fjx-1)
For $v2 = $fjx To $m-1
        _xh($aArray[$v2],String($aArray[$v2])&"+",$fjx-1)
Next
_ArrayDelete($display, 0)
$dif = TimerDiff($begin)
ConsoleWrite("耗时:"&$dif&',数组个数:'&UBound($display))
;_ArrayDisplay($display,"耗时:"&$dif)


Func _xh($var,$str,$n)
        $i_step = 10000
        Local $a_temp[$i_step][3], $i_cnt = 1;
        $a_temp[0][0] = 1
        $a_temp[1][0] = $var
        $a_temp[1][1] = $str
        $a_temp[1][2] = $n
        Local $num, $i, $i_temp
        While ($a_temp[0][0] <= $i_cnt)
                $i_temp = $a_temp[0][0]
                $var = $a_temp[$i_temp][0]
                $str = $a_temp[$i_temp][1]
                $n = $a_temp[$i_temp][2]
        For $i = $n To 0 Step -1
                        $num = Execute("$var + $aArray[$i]")
                        Switch $num
                                Case 105 To 1500
                                        ContinueLoop
                                Case 102 To 105
                                        _ArrayAdd($display,$str&String($aArray[$i])&"="&String($num))
                                Case 1 To 102
                                        $i_cnt += 1;根据需要决定是否判断数组超界ReDim
                                        If $i_cnt>=UBound($a_temp,1) Then ReDim $a_temp[UBound($a_temp,1)+$i_step][3]
                                        $a_temp[$i_cnt][0] = $num
                                        $a_temp[$i_cnt][1] = $str&String($aArray[$i]&"+")
                                        $a_temp[$i_cnt][2] = $i-1
                        EndSwitch
        Next
                $a_temp[0][0] += 1
        WEnd
EndFunc

afan

回复 44# 阿福


    感谢前辈指点~！