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

afan · 发表于 2010-1-20 03:55:32

本帖最后由 afan 于 2012-3-15 09:48 编辑

比如有如下15个数，任意N个数组合，使之和在 102到105 之间（102>和值<105）的所有可能的组合或任意一个组合(此为延伸问题)：

Dim $aArray[15] = [51, 8, 13, 2, 52, 61, 37, 85, 19, 11, 7, 62, 22, 38, 79]

本人菜鸟，运算耗时2.7xx 秒。请教各位高手有无高效的方法。
以下为本人写的代码，为不影响各位的思维，暂隐藏。

游客，如果您要查看本帖隐藏内容请回复

lxz · 发表于 2010-1-20 08:13:29

学习一下......

ndyndy · 发表于 2010-1-20 08:53:01

还是先看看原麻

maxkingmax · 发表于 2010-1-20 09:01:59

不行，想不出来，看一下！

zcx880517 · 发表于 2010-1-20 09:30:40

学习下，，好知识

hzxymkb · 发表于 2010-1-20 10:00:30

楼主那么晚还不睡觉！还在研究！真是佩服！
不过我真的想不出来！还是看看源码先吧！

顽固不化 · 发表于 2010-1-20 10:00:47

不知道怎么弄，这属于“智能”问题，我却是愚蠢的。

顽固不化 · 发表于 2010-1-20 10:01:24

不知道怎么弄，这属于“智能”问题，我却是愚蠢的。

wjc826194 · 发表于 2010-1-20 10:02:55

???????????????

afan · 发表于 2010-1-20 11:35:55

各位就别谦虚了，我这不是限制题（限制的话我也解不出~~），什么都可以上~

FBWOLF · 发表于 2010-1-20 11:55:27

本人X鸟+懒鸟,本有个构思,却懒于下手!只好先睹AFAN大大代码了!

sanmoking · 发表于 2010-1-20 12:13:29

本帖最后由 sanmoking 于 2010-1-25 18:57 编辑

0.3秒快不？
代码隐藏，afan要多多加分啊。。。

游客，如果您要查看本帖隐藏内容请回复

上边的代码有问题,
如果数组最后边有0,1之类的数在得到51+8+37+7=103结果之后就不会再往下计算了,
比如51+8+37+7+1=104,更不会有51+8+37+7+1+0=104，现更正如下:

 
#include <Array.au3>
Dim $aArray[15] = [51, 8, 13, 2, 52, 61, 37, 85, 19, 11, 7, 62, 22, 38, 79];~ _ArraySort($aArray)
GUICreate("", 400, 620)
GUICtrlCreateEdit("", 10, 10, 380, 600)
$coo = 0 ;存储计算次数
$com = 0;存储正确结果数量
$num = UBound($aArray) - 1 ;计算数组最后一位
$begin = TimerInit();开始计时
mimi(0, 0, "")
$dif = TimerDiff($begin);结束记时

GUICtrlSetData(-1, "计算耗时: " & $dif&@CRLF,1)
GUICtrlSetData(-1, "总计计算了"&$coo&"次加法运算"&@CRLF,1)
GUICtrlSetData(-1, "正确结果有"&$com&"种算法"&@CRLF,1)
GUISetState()
While GUIGetMsg() + 3
WEnd
Func mimi($k, $resd, $txtd)
                For $i = $k To $num
                        $resx = $resd + $aArray[$i]
                        $txtx = $txtd & $aArray[$i] & "+"
                        $coo += 1 
                        If $resx <= 102 Then                                        
                                mimi($i + 1, $resx, $txtx)                        
                        ElseIf $resx > 102 And $resx < 105 Then
                                GUICtrlSetData(-1, StringReplace($txtx & "=", "+=", "=") & $resx&@CRLF,1)
                                $com += 1 
;~ --------------------------------下边这句必须加上的-----------------------                                
                                mimi($i + 1, $resx, $txtx)        
;~ -------------------------------------------------------------------------   
                        EndIf
                Next
EndFunc   ;==>mimi

;~ 之所以犯错,就是因为afan的题目直接是103,104两个结果,这两个相差为1,并且它提供的数组里面正好没有1,所以测试一下结果对上46就以为通过了
;~ 不加上面这句,如果得到一个51+13+2+19+11+7=103的结果,1在7之前,可以把1算上,1在7之后,就不会去计算了
;~ 假如题目要求是100,110之间的结果,那么比如51+13+2+19+11+5+7=108这样的结果就不会得到,
;~ 只会得到51+13+2+19+11+5=101,符合结果范围,就不在去加后边的7了
;~ 本代码上面的数组最后添加一个0,就会发现结果是92个,因为添加了一个0,所以46个结果每个加上0,还是符合的,所以结果翻了一倍变成92个了.

sanmoking · 发表于 2010-1-20 12:21:39

本帖最后由 sanmoking 于 2010-1-25 18:49 编辑

楼上的代码，我直接双击au3运行，结果是

计算耗时: 21.4052344641568
总计计算了2651次加法运算
正确结果有46种算法

编译成exe之后，

计算耗时: 21.5873805190324
总计计算了2651次加法运算
正确结果有46种算法

差不多时间

afan的代码我没都运行成功，也没仔细看afan的原理，应该跟我的不一样。。从排序上就能看出来。
另外验证有单一数字符合102-105的和0的情况下的计算结果.
如下：
Dim $aArray[20] = [51, 8, 13, 2, 52, 61, 37,0, 85,103, 19, 11, 7, 62, 22, 38, 79,106,104,1]
结果：

51+8+13+2+0+19+11=104
51+8+13+2+0+7+22=103
51+8+13+2+0+7+22+1=104
51+8+13+2+19+11=104
51+8+13+2+7+22=103
51+8+13+2+7+22+1=104
51+8+13+0+19+11+1=103
51+8+13+19+11+1=103
51+8+2+0+19+22+1=103
51+8+2+19+22+1=103
51+8+37+0+7=103
51+8+37+0+7+1=104
51+8+37+7=103
51+8+37+7+1=104
51+8+0+7+38=104
51+8+7+38=104
51+13+2+37=103
51+13+2+37+0=103
51+13+2+37+0+1=104
51+13+2+37+1=104
51+13+2+0+19+11+7=103
51+13+2+0+19+11+7+1=104
51+13+2+0+38=104
51+13+2+19+11+7=103
51+13+2+19+11+7+1=104
51+13+2+38=104
51+13+0+11+7+22=104
51+13+0+38+1=103
51+13+11+7+22=104
51+13+38+1=103
51+2+0+11+38+1=103
51+2+11+38+1=103
51+52=103
51+52+0=103
51+52+0+1=104
51+52+1=104
51+0+19+11+22=103
51+0+19+11+22+1=104
51+19+11+22=103
51+19+11+22+1=104
8+13+2+52+0+7+22=104
8+13+2+52+7+22=104
8+13+2+61+0+19=103
8+13+2+61+0+19+1=104
8+13+2+61+0+11+7+1=103
8+13+2+61+19=103
8+13+2+61+19+1=104
8+13+2+61+11+7+1=103
8+13+2+0+19+62=104
8+13+2+0+19+22+38+1=103
8+13+2+0+11+7+62=103
8+13+2+0+11+7+62+1=104
8+13+2+0+79+1=103
8+13+2+19+62=104
8+13+2+19+22+38+1=103
8+13+2+11+7+62=103
8+13+2+11+7+62+1=104
8+13+2+79+1=103
8+13+52+0+19+11=103
8+13+52+0+19+11+1=104
8+13+52+0+7+22+1=103
8+13+52+19+11=103
8+13+52+19+11+1=104
8+13+52+7+22+1=103
8+13+61+0+22=104
8+13+61+22=104
8+13+37+0+7+38=103
8+13+37+0+7+38+1=104
8+13+37+7+38=103
8+13+37+7+38+1=104
8+13+0+19+62+1=103
8+13+19+62+1=103
8+2+52+0+19+22=103
8+2+52+0+19+22+1=104
8+2+52+0+11+7+22+1=103
8+2+52+19+22=103
8+2+52+19+22+1=104
8+2+52+11+7+22+1=103
8+2+61+0+11+22=104
8+2+61+11+22=104
8+2+37+0+19+38=104
8+2+37+0+11+7+38=103
8+2+37+0+11+7+38+1=104
8+2+37+19+38=104
8+2+37+11+7+38=103
8+2+37+11+7+38+1=104
8+2+0+85+7+1=103
8+2+0+19+11+62+1=103
8+2+85+7+1=103
8+2+19+11+62+1=103
8+52+37+0+7=104
8+52+37+7=104
8+61+0+11+22+1=103
8+61+11+22+1=103
8+37+0+19+11+7+22=104
8+37+0+19+38+1=103
8+37+19+11+7+22=104
8+37+19+38+1=103
8+0+85+11=104
8+0+11+62+22=103
8+0+11+62+22+1=104
8+85+11=104
8+11+62+22=103
8+11+62+22+1=104
13+2+52+37=104
13+2+52+37+0=104
13+2+52+0+19+11+7=104
13+2+52+19+11+7=104
13+2+61+0+19+7+1=103
13+2+61+19+7+1=103
13+2+37+0+19+11+22=104
13+2+37+19+11+22=104
13+2+0+19+7+62=103
13+2+0+19+7+62+1=104
13+2+19+7+62=103
13+2+19+7+62+1=104
13+52+37+0+1=103
13+52+37+1=103
13+52+0+19+11+7+1=103
13+52+0+38=103
13+52+0+38+1=104
13+52+19+11+7+1=103
13+52+38=103
13+52+38+1=104
13+61+0+19+11=104
13+61+0+7+22=103
13+61+0+7+22+1=104
13+61+19+11=104
13+61+7+22=103
13+61+7+22+1=104
13+37+0+19+11+22+1=103
13+37+19+11+22+1=103
13+0+19+11+22+38=103
13+0+19+11+22+38+1=104
13+0+11+79=103
13+0+11+79+1=104
13+0+7+62+22=104
13+19+11+22+38=103
13+19+11+22+38+1=104
13+11+79=103
13+11+79+1=104
13+7+62+22=104
2+52+37+0+11+1=103
2+52+37+11+1=103
2+52+0+19+7+22+1=103
2+52+0+11+38=103
2+52+0+11+38+1=104
2+52+19+7+22+1=103
2+52+11+38=103
2+52+11+38+1=104
2+61+0+19+22=104
2+61+0+11+7+22=103
2+61+0+11+7+22+1=104
2+61+19+22=104
2+61+11+7+22=103
2+61+11+7+22+1=104
2+37+0+19+7+38=103
2+37+0+19+7+38+1=104
2+37+19+7+38=103
2+37+19+7+38+1=104
2+0+11+7+62+22=104
2+0+62+38+1=103
2+0+22+79=103
2+0+22+79+1=104
2+11+7+62+22=104
2+62+38+1=103
2+22+79=103
2+22+79+1=104
52+0+19+11+22=104
52+19+11+22=104
61+0+19+22+1=103
61+19+22+1=103
37+0+7+22+38=104
37+7+22+38=104
0+85+19=104
0+85+11+7=103
0+85+11+7+1=104
0+103=103
0+103+1=104
0+19+62+22=103
0+19+62+22+1=104
0+11+7+62+22+1=103
0+104=104
85+19=104
85+11+7=103
85+11+7+1=104
103=103
103+1=104
19+62+22=103
19+62+22+1=104
11+7+62+22+1=103
104=104
计算耗时: 81.7307786324798
总计计算了10338次加法运算
正确结果有192种算法

afan · 发表于 2010-1-20 12:24:29

回复 12# sanmoking

高手就是高手，学习了~！

fsldn · 发表于 2010-1-20 12:24:59

先看一下，学习学习

		自动登录	找回密码
密码			加入

[效率算法] 从一组数字中任意组合N个数字，使之和在某个数值范围

本帖子中包含更多资源

评分

本帖子中包含更多资源