获取数组组合(JS)的最接近值 [英] Get the closest value for combinations of an array (JS)

问题描述

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

I'm looking for an algorithm that I can use for combining values in array, to get as close as possible to "another value".

例如，我想找出关闭结果的组合是2.5.我的数组是 [0.5、1.0、1.5、2.0、3.0] .在这种情况下，组合为 2.0 + 0.5 .

For instance, the number I want to find out what combination that gives the closes result to is 2.5. And my array is [0.5, 1.0, 1.5, 2.0, 3.0]. The combination in this case would be 2.0+0.5.

2.7将产生相同的组合(最接近2.5)，而3.7将产生 3.0 + 0.5 ，而7.0将产生 3.0 + 3.0 + 1.0 .

2.7 would yield the same combo (2.5 is the closest), while 3.7 would yield 3.0+0.5 and 7.0 would be 3.0+3.0+1.0.

我一直在研究不同的算法以创建可用的组合，例如-例如:

I've been reading up on different algorithms to create available combinations and such – for instance this one: https://codereview.stackexchange.com/questions/7001/better-way-to-generate-all-combinations However, I'm having difficulties to write a function that allows for the same value to be used multiple times (like my example with 7.0). This makes the number of combinations quite large.

有人有好榜样吗?还是有什么要指教的?

Anyone having a good example tucked away? Or have any pointers to give?

编辑@zkar告诉我有关背包问题"的信息.我可能还会补充一点，在我的示例中，所追求的值在指定的范围内(1.0和10.0)，这在一定程度上限制了组合.

EDIT @zkar told me about the "knapsack problem". I may add that for my example, the sought after value are in a specified range (1.0 and 10.0) – which limits the the combinations somewhat.

推荐答案

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

如果仅使用一次硬币:

给出一组值S，n = | S |，m:要近似的值

Given a set of values S, n = |S|, m: value to approximate

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 ² )

This algorithm runs in Time: O(|S|²) ~ O(n²)

Set BEST将具有n个解决方案，每K个:1..n

The Set BEST will have n solutions, for each K: 1..n

对于K:您在那个阶段拥有最佳选择

for K: you have the optimal choice at that stage

找到完整的解决方案:

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中:

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

这篇关于获取数组组合(JS)的最接近值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！