在一组数中寻找加和最接近某个值的数组合 |
您所在的位置：网站首页 › 一组一组 › 在一组数中寻找加和最接近某个值的数组合 |
|
在一组数中寻找加和最接近某个值的数组合
今天碰到个小问题，就是需要在一组数中，找到加和数最接近某个值的一系列数。 比如： [8.05, 6.98, 6.19, 5, 22.96,4.71,4.74,4.25,6.34,2.77,7.31,3.59,18.28,19.55] 中找到最接近84.01的一组数。 这个问题，所有的可能元素的加和组合数为16383，即： Binomial[14, 1] + Binomial[14, 2] + Binomial[14, 3] + Binomial[14, 4] + Binomial[14, 5] + Binomial[14, 6] + Binomial[14, 7] + Binomial[14, 8] + Binomial[14, 9] + Binomial[14, 10] + Binomial[14, 11] + Binomial[14, 12] + Binomial[14, 13] + Binomial[14, 14] 用mathematica软件如果求加和等于给定值的计算在mathematica软件中是很方便的，两句话就能搞定了。 array = Subsets[{8.05, 6.98, 6.19, 5, 22.96, 4.71, 4.74, 4.25, 6.34, 2.77, 7.31, 3.59, 18.28, 19.55}, 13]; Do[sumt = Total[array[[i]]]; If[sumt == 84.01, Print[array[[i]]]], {i, 1, Length[array]}]结果为： {6.98,6.19,5,22.96,4.71,4.74,4.25,7.31,3.59,18.28}其中用到的函数是Subsets用于抽取list中元素的组合，13不带花括号则组合包括对所有数量小于等于13的情况。 如果要计算接近的情况，比如相差0.02的情况： array = Subsets[{8.05, 6.98, 6.19, 5, 22.96, 4.71, 4.74, 4.25, 6.34, 2.77, 7.31, 3.59, 18.28, 19.55}, 13]; Do[err = Abs[Total[array[[i]]] - 84.01]; If[err < 0.02, If[err == 0, Print[err, array[[i]]]; Break[], Print[err, array[[i]]]]], {i, 1, Length[array]}]结果为： 0.02{8.05,6.19,22.96,4.71,4.25,18.28,19.55} 0.01{8.05,6.19,22.96,4.74,4.25,18.28,19.55} 0.02{8.05,22.96,4.25,7.31,3.59,18.28,19.55} 0.01{6.19,5,22.96,4.71,7.31,18.28,19.55} 0.02{6.19,5,22.96,4.74,7.31,18.28,19.55} 0.02{8.05,6.98,6.19,5,22.96,4.71,4.25,6.34,19.55} 0.02{8.05,6.98,5,22.96,4.25,6.34,7.31,3.59,19.55} 0.{6.98,6.19,5,22.96,4.71,4.74,4.25,7.31,3.59,18.28}但实际上用mathematica软件做数值计算并不是非常合适，如果语句写的不好，那么很容易卡死。 使用python进行计算其实最新想到的，并实践的是利用python来解决。这可能跟当前的知识应用状态相关，第一反应就是试图联系线性规划，如果有现成的求解器，那么就不用算了，但略一思索，似乎是不能用的。反而只是一些简单的加和，应该就可以解决。然后第二反应是怎么来解决，没有精确等于解的情况，我想这应该是一个范围，既能得到临界大于，也能得到临界小于的解。所以很自然想到排列，给出一个排列，那么从头计算到尾，自然能够得到最接近解的小于和大于的值。 所以首先实现了一个基于排列的蒙特卡洛方法解： def MC_permutation(): data1=[] res_data=[] res_j=0 res_jp=0 res_s1=0 res_s2=0 res_err=100.0 outflag=False for i in range(200000): data1[:]=data[:] random.shuffle(data1) #print("data1=",data1) sumt=0 for j in range(len(data1)): sumts=sumt sumt=sumt+data1[j] if(sumt>suma): ds1=abs(sumts-suma) ds2=abs(sumt-suma) ds=min(ds1,ds2) if (ds < res_err): #print('') #print('ds=',ds) #print('i=',i,'data1=',data1) #print('j=',j,data1[j]) #print('sum=',sumts,sumt) res_err=ds res_data[:]=data1[:] res_jp=j if (ds1 < ds2): res_j=j else: res_j=j+1 #print(ds1,ds2) #print(j,res_j) res_s1=sumts res_s2=sumt if(ds |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |