获取数组(JS)组合的最接近的值

Get the closest value for combinations of an array (JS)

本文关键字：最接近 组合 数组 JS 获取      更新时间：2023-09-26

我正在寻找一种算法，我可以用于组合数组中的值，以尽可能接近"另一个值"。

例如，我想找出什么组合会产生关闭的结果是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演示):

/**
 * @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;
}

你的问题是硬币问题和背包问题的混合

如果硬币只使用一次:

给定一组值S, n = |S|， m:近似值

DEFINE BEST = { }
DEFINE SUM = 0
DEFINE K = 0
WHILE S IS NOT EMPTY DO
    K = K + 1
    FIND MIN { Si : |(SUM+Si) - m| is minimal }
    ADD TUPLE < Si, |(SUM+Si) - m|, K > to BEST
    SUM = SUM + Si
    REMOVE Si from S
END-FOR
RETURN BEST

这个算法运行时间:O(| | <一口> 2> 2> p>对于每个K，集合BEST将有n个解:1..n

对于K，你在该阶段有最优选择

找到完整的解决方案:

GIVEN BEST = { < COIN:X, DISTANCE:Y, DEGREE:K > }
DEFINE SOLUTION = { }
Y" = MINIMUM Y IN BESTi.Y for i: 1..n
KEEP ADDING BESTj.X to SOLUTION UNTILL BESTj.Y = Y" FOR j: 1..n

如果硬币可以重复使用:

DEFINE SOLUTION = { }
DEFINE SUM = 0
LESS = { Si : Si < m }
SORT LESS IN DESCENDING ORDER
FOR Li in LESS DO
    WHILE (SUM+Li) <= m DO
        SUM = SUM + Li
        ADD Li TO SOLUTION
    END-WHILE
    IF SUM = m THEN BREAK-FOR
END-FOR
RETURN SOLUTION
在JavaScript: 

function coinProblem (var coins, var value)
{
    var solution = new Array();
    var sum = 0;
    var less = new Array();
    for (var i in coins)
        if (i <= value)
            less.push(i);
    // sort in descending order
    less.sort();
    less.reverse();
    for (var i in less)
    {
        while ((sum+i) <= value)
        {
            solution.push(i);
            sum = sum + i;
        }
        if (sum == value) break;
    }
    return solution;
}
相关文章：