获取数组中组合最接近的值（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），这在一定程度上限制了组合的数量。

- Marcus Olsson

---

看看这个背包问题。在我看来，这是你应该阅读的内容。 - zkar

虽然我同意这可能属于“背包问题”，但仍然存在一个区别，即我只需要担心一种类型的价值（比如维基百科示例中的重量），而不是两种。 - Marcus Olsson

请检查一下这是否合适：http://jsfiddle.net/fedosov/p8xZM/5/ 所提供的三个示例都是有效的。 - fedosov

@Marcus，我发布了一篇带有修改建议的答案。 - fedosov

在组合搜索问题中，这个问题最接近子集和问题（参见：http://en.wikipedia.org/wiki/Subset_sum_problem）。然而，它***不是***一个组合搜索问题，如果我没记错的话，它是一个幂集搜索问题，而且要得到精确答案会更加棘手（并且计算复杂度更高）。 - RBarryYoung

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;
}

- Khaled.K

---

嗯，如果我理解正确的话，这不就是一种贪心启发式算法吗？它并不总是能返回精确答案，对吧？ - RBarryYoung

与fedesov的解决方案相似，如果我传递S={0.4,1.0}, m=0.8，我认为您的算法会返回{1.0}而不是正确的{0.4,0.4}。 - RBarryYoung

@RBarryYoung 的FIND MIN { Si : |(SUM+Si) - m| is minimal }意思是：找到使得 |(SUM+Si) - m| 最小的 Si。我的解决方案是采用动态规划和贪心启发式算法。 - Khaled.K

如果硬币可以重新使用，那么算法将会不同..让我修复我的解决方案。 - Khaled.K

第二个算法是贪心算法，它是最优的，因为它最大化了拟合。 - Khaled.K

Answer 2

你可以尝试这个简单的算法（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;
}

- fedosov

---

对于参数 src={0.4,1.0}, val=0.8，返回的答案应该是 {0.4,0.4}，但是这个算法返回了 {1.0}。 - RBarryYoung

经过运行更多的测试，我在某些情况下得到了一些奇怪的结果。例如，当 src = [0.5, 1.0, 1.25, 1.5, 2.0, 3.0] 和 val = 1.44 时，应该得到 result = [1.5]。但是我得到的是 result = [1.25, 0.5]。这确实很棘手 =) 看看 @khaleds 的解决方案，看看能否将其应用到你的代码中。 - Marcus Olsson

对于 source = 2、3 和 val = 4，此代码返回 3，但应该是 2+2=4。 - timlg07