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

Question

我正在寻找一种算法,我可以用它来组合数组中的值,以尽可能接近"另一个值".

例如,我想要找出给出结果结果的组合的数字是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) - 这在某种程度上限制了组合.

Answer 1

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

如果硬币仅使用一次：

给定一组值 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(|S| ² ) ~ O(n ² )

BEST 集合将有 n 个解决方案，对于每个 K：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;
}