求个算法,能给分析分析嘛。从N个数中随机取M个不同的数进行求和,返回这个求和集合中的小于Y的最大值

J2EE 码拜 9年前 (2016-03-19) 1556次浏览
从N个数中随机取M个不同的数进行求和,返回这个求和集合中的小于Y的最大值。
例如:从50, 55, 56, 57, 58,(N = 5),中取3个数(M=3),求和的集合中小于163的最大值是多少?
和集合为:
[161, 162, 163, 163, 164, 165, 168, 169, 170, 171]
返回结果:162
解决方案

10

本人竟然没看懂求个算法,能给分析分析嘛。从N个数中随机取M个不同的数进行求和,返回这个求和集合中的小于Y的最大值

10

从N个数中随机取M个不同的数进行求和,返回这个求和集合中的小于Y的最大值。
这玩意儿就是个穷举,随机选取M个实际上就是从N个数中选出M个的全部情况,然后求和
思路很简单
1、N个数从小到大排好序,主要是优化算法
2、用大小为M的数组记录下标,为了依次算出全部组合
3、M数组满足:a、每个元素不能大于N-1,b、前面的元素必须必后面的小
4、在3的条件下依次+1,实际上就是一个N进制的数组
5、当依次加到某个和大于Y时,停止算法,后面的和肯定比Y大
6、推进过程中需要记录最大值,算法结束时该最大值就是你需要的
(50, 55, 56, 57, 58)选三个
下标数组依次是 012  013 014  023 024 034 123 124 134  234(这个算法是需要你实现的),至于算法优化,最大值如第5条可以优化,最小值部分的优化,本人考虑了

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明求个算法,能给分析分析嘛。从N个数中随机取M个不同的数进行求和,返回这个求和集合中的小于Y的最大值
喜欢 (0)
[1034331897@qq.com]
分享 (0)