Question

如何将几个数字进行搭配相加，得出指定区间的组合（求算法或代码，javascript/VB/C#均可）

比如我这里有15个数字，5.6、18.7、23.5、39、13.2、14.9、13.7、10.1、9.2、9.9、16.5、17.3、20.8、20.2、17。

我需要用随便几个数字搭配相加得出结果为50~55区间的若干组合，请问如何写这样的代码？
请写出代码参考，谢谢！本题200分

Answer 1

k4me的算法基本上已经是最简单的了，比我想的优化了10多倍，我按照他的算法把自己代码整理了一下，贴出来大家指正

var RANGE_MAX = 55;
var RANGE_MIN = 50;
function sumArr(arr){
var sum = 0;
for(var i=0;i<arr.length;i++){
sum+=arr[i];
}
return sum;
}
function toBasicStr(num){
return num.toString(2)
}
function getAllGroup(arr){
var maxNumber = 1;
for(var i=1;i<arr.length;i++){
maxNumber *= 2;
}
var resultArr = [];
for(var i=0;i<maxNumber;i++){
var str = toBasicStr(i);
var tempArr = [];
for(var j=0;j<str.length;j++){
if(str[j] == "1"){tempArr.push(arr[arr.length - str.length + j]);}
}
var sum = sumArr(tempArr);
if(sum <= RANGE_MAX && sum >= RANGE_MIN){resultArr.push(tempArr)}
}
return resultArr;
}
var result = getAllGroup([5.6,18.7,23.5,39,13.2,14.9,13.7,10.1,9.2,9.9,16.5,17.3,20.8,20.2,17]);
for(var i=0;i<result.length;i++){
document.write(result[i] + "<br/>");
}

Answer 2

方式,穷举
过程,先将15个数字放进数组,将所有数字组合的排列看做15位的2进制序列,比如1001代表数组内倒数第一和第四位参与加法.如此有2^15=32768种组合.
一个循环,变量每次+1,将其转换为2进制,比如100100100100100,然后将数值为"1"的位对应从数组提取数值,所有数值相加,然后判断符合50-55,输出.
过程中不断提纯可以让效率提高一些,就是加限制,比如一个组合已经超过55,则再加入任何数值都会超过55
....数值比较乱,限制比较随机,不容易找出什么蹊跷算法.
--------
代码非J/v/c
(o my god!)
所以就不贴了,你会那么多语言,想必看我写的过程也能写出的.:)

http://www.fileden.com/files/2007/5/8/1059086/k4me_15-pk-n-sum.rar

Answer 3

假如输入数据都是比较小的整数(在1000以下吧)，可以利用动态规划快速求解这个问题

令f[i][j][k]表示选择到第i个数字 区间在[j,k]中和最小的方案数总和
则DP方程如下

f[i][j][k]
= f[i-1][j-n[i]][k-n[i]] + f[i-1][j][k] (i>0),
= 1 (i=0,n[i] in [j,k]),
= 0 (i=0,n[i] not in [j,k])

如果不是整数 可以用HASH表代替数组 同样可以完成这样的功能
选择的同时可以保存方案 后面就能DFS搜索出方案解法

比起枚举 DP的计算量小得多 从指数级别下降到了多项式级别

当然如果你的数据量比较小的话不会有什么区别 但是数据量大了指数级别的算法就会很耗时间 无法完成计算
这个算法的时间复杂度为O(ijk)+O(i^2)
简化为O(n^3)

Answer 4

int[] array = new int[15];
//赋值省略,以下数组随机排序
Random rnd = new Random();
for (int i = 0; i < 15; i++)
{
int pos = rnd.Next(i, 15);
int temp = array[pos];
array[pos] = array[i];
array[i] = temp;
}
//以下双层循环,顺序相加,结果为50~55区间则返回,略

Answer 5

最简单的~ 枚举法呗
最外面套一个循环 2 到 15 决定使用几个数字
里面的循环 就依次选择数字
如果如何要求就显示结果..

ok了