11

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

例如，我想找出给出关闭结果的组合的数字是 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）——这在一定程度上限制了组合。

4

2 回答 2

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| 2 ) ~ O(n 2 )

Set BEST 将有 n 个解，对于每个 K：1..n

for 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;
}
于 2013-04-14T12:06:50.037 回答
1

您可以尝试这个简单的算法（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;
}
于 2013-04-14T12:24:17.343 回答