Получите самое близкое значение для комбинаций массива (JS)

Я ищу алгоритм, который я могу использовать для объединения значений в массиве, чтобы как можно ближе подойти к "другому значению".

Например, число, которое я хочу узнать, какая комбинация дает результат закрытия, равна 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/info/7001/better-way-to-generate-all-combinations Однако у меня возникают трудности с написанием функция, которая позволяет использовать одно и то же значение несколько раз (например, мой пример с 7.0). Это делает количество комбинаций довольно большим.

Любой, имеющий хороший пример, спрятан? Или у вас есть указатели?

ИЗМЕНИТЬ @zkar рассказал мне о "проблеме рюкзака". Я могу добавить, что для моего примера искомое значение находится в заданном диапазоне (1.0 и 10.0), что несколько ограничивает комбинации.

Ответ 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;
}

Ответ 2

Вы можете попробовать этот простой алгоритм (JSFiddle demo):

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