我正在寻找一个算法,我可以使用它来组合数组中的值,以尽可能接近“另一个值”.
例如,我想找出给出关闭结果的组合的数量是2.5.而我的阵列是[0.5,1.0,1.5,2.0,3.0].在这种情况下的组合将为2.0 0.5.
2.7将产生相同的组合(2.5是最接近的),而3.7将产生3.0±0.5,7.0将为3.0±3.0±1.0.
我一直在阅读不同的算法来创建可用的组合,例如这个：https://codereview.stackexchange.com/questions/7001/better-way-to-generate-all-combinations但是,我很难编写一个允许多次使用相同值的函数(像我的例子7.0 ).这使得组合的数量相当大.
有一个很好的例子呢？还是有任何指针给？
编辑
@zkar告诉我有关“背包问题”.我可以补充说,对于我的例子,追求的值在一个指定的范围(1.0和10.0) – 这有限的组合.
解决方法
你可以尝试这个简单的算法(
JSFiddle demo)：
/**
* @param src {Array} List of available values
* @param val {Number} Target value
* @returns {Array}
*/
function get_combinations(src,val)
{
var result = [];
var source = src.slice();
source.sort();
while (val > 0)
{
for (var i = source.length - 1; i >= 0; i--)
{
if (source[i] <= val || i == 0)
{
val = val - source[i];
result.push(source[i]);
break;
}
}
}
return result;
}
