Найдите возможные числа в массиве, которые могут суммироваться с целевым значением

Учитывая, что у меня есть массив чисел, например [14,6,10]. Как я могу найти возможные комбинации/пары, которые могут составить заданное целевое значение.

например, у меня есть [14,6,10], я ищу целевое значение 40, мой ожидаемый результат будет

 10 + 10 + 6 + 14
 14 + 14 + 6 + 6
 10 + 10 + 10 + 10

* Порядок не важен

С учетом сказанного, это то, что я пробовал до сих пор:

function Sum(numbers, target, partial) {
  var s, n, remaining;

  partial = partial || [];

  s = partial.reduce(function (a, b) {
    return a + b;
  }, 0);

  if (s === target) {
     console.log("%s", partial.join("+"))
  }


  for (var i = 0; i < numbers.length; i++) {
    n = numbers[i];
    remaining = numbers.slice(i + 1);
    Sum(remaining, target, partial.concat([n]));
  }
}

>>> Sum([14,6,10],40);
// returns nothing

>>> Sum([14,6,10],24);
// return 14+10

На самом деле это бесполезно, так как он вернется только в том случае, если число можно использовать только один раз для суммирования.

Итак, как это сделать?


javascript sum algorithm
person user7716943    schedule 09.02.2019    source источник
comment
у вас тоже есть отрицательные числа?   -  person Nina Scholz    schedule 09.02.2019
comment
@Нина только положительные числа без отрицательных   -  person user7716943    schedule 09.02.2019
comment
[14,6,10], так это длина + 1, т.е. комбинация из 4 чисел? Кроме того, что если у вас есть дубликаты в вашем массиве   -  person Monica Acha    schedule 09.02.2019

Ответы (2)


arrow_upward
5
arrow_downward

Вы можете добавить значение фактического индекса, если сумма меньше желаемой суммы, или перейти к следующему индексу.

function getSum(array, sum) {
    function iter(index, temp) {
        var s = temp.reduce((a, b) => a + b, 0);
        if (s === sum) result.push(temp);
        if (s >= sum || index >= array.length) return;
        iter(index, temp.concat(array[index]));
        iter(index + 1, temp);
    }

    var result = [];
    iter(0, []);
    return result;
}

console.log(getSum([14, 6, 10], 40));
.as-console-wrapper { max-height: 100% !important; top: 0; }

Для получения ограниченного набора результатов вы можете указать длину и проверить ее в условии выхода.

function getSum(array, sum, limit) {
    function iter(index, temp) {
        var s = temp.reduce((a, b) => a + b, 0);
        if (s === sum) result.push(temp);
        if (s >= sum || index >= array.length || temp.length >= limit) return;
        iter(index, temp.concat(array[index]));
        iter(index + 1, temp);
    }

    var result = [];
    iter(0, []);
    return result;
}

console.log(getSum([14, 6, 10], 40, 5));
.as-console-wrapper { max-height: 100% !important; top: 0; }

person Nina Scholz    schedule 09.02.2019
comment
именно то, что мне было нужно! - person user7716943; 09.02.2019
comment
во-первых, если мне нравится getSum([1, 2, 3], 20), как мне явно вывести только результаты, если длина массива равна/ниже x? - person user7716943; 09.02.2019
comment
добавьте сюда условие: if (s >= sum || index >= array.length || temp.length >= x) return; это условие выхода для ресурса. - person Nina Scholz; 09.02.2019

arrow_upward
5
arrow_downward

TL&DR: перейдите к части II, чтобы узнать правду

Часть I

Ответ @Nina Scholz на эту фундаментальную проблему просто показывает нам прекрасное проявление алгоритма. Честно говоря, это меня сильно смутило по двум причинам.

  1. Когда я пытаюсь выполнить [14,6,10,7,3] с целью 500, она делает 36 783 575 вызовов функции iter без разрыва стека вызовов. Тем не менее, память не показывает значительного использования вообще.
  2. Мое решение для динамического программирования работает немного быстрее (а может и нет), но оно никак не может справиться с описанным выше случаем, не исчерпав 16 ГБ памяти.

Так что я отложил свое решение и вместо этого начал немного исследовать ее код в инструментах разработки и обнаружил как его красоту, так и некоторые его недостатки.

Во-первых, я считаю, что этот алгоритмический подход, который включает в себя очень умное использование рекурсии, возможно, заслуживает отдельного названия. Это очень эффективно использует память и использует память только для созданного набора результатов. Стек динамически растет и непрерывно сжимается до предела, близкого к его пределу.

Проблема в том, что, будучи очень эффективным, он все же делает огромное количество избыточных вызовов. Итак, глядя на это, с небольшой модификацией 36 783 575 вызовов iter можно сократить до 20 254 744... например, 45%, что дает гораздо более быстрый код. Дело в том, что входной массив должен быть отсортирован по возрастанию.

Итак, перед вами модифицированная версия алгоритма Нины. (Будьте терпеливы .. для завершения потребуется 25 секунд)

function getSum(array, sum) {
    function iter(index, temp) {cnt++ // counting iter calls -- remove in production code
        var s = temp.reduce((a, b) => a + b, 0);
        sum - s >= array[index]   && iter(index, temp.concat(array[index]));
        sum - s >= array[index+1] && iter(index + 1, temp);
        s === sum                 && result.push(temp);
        return;
    }

    var result = [];
    array.sort((x,y) => x-y); // this is a very cheap operation considering the size of the inpout array should be small for reasonable output.
    iter(0, []);
    return result;
}
var cnt = 0,
    arr = [14,6,10,7,3],
    tgt = 500,
    res;
console.time("combos");
res = getSum(arr,tgt);
console.timeEnd("combos");
console.log(`source numbers are ${arr}
found ${res.length} unique ways to sum up to ${tgt}
iter function has been called ${cnt} times`);

Часть II

Несмотря на то, что я был впечатлен производительностью, мне не понравилось вышеприведенное решение без какой-либо серьезной причины, которую я могу назвать. Меня беспокоило то, как это работает с побочными эффектами и очень трудно понять двойную рекурсию и тому подобное.

Итак, вот мой подход к этому вопросу. Это во много раз эффективнее по сравнению с принятым решением, несмотря на то, что я работаю в JS. У нас все еще есть место, чтобы сделать его немного быстрее с помощью уродливых императивных способов.

Разница в том, что;

Заданные числа: [14,6,10,7,3] Целевая сумма: 500

Принятый ответ:

  • Количество возможных ответов: 172686
  • Разрешается за: 26357 мс
  • Количество рекурсивных вызовов: 36783575

Ответ ниже

  • Количество возможных ответов: 172686
  • Разрешается через: 1000 мс
  • Количество рекурсивных вызовов: 542657

function items2T([n,...ns],t){cnt++ //remove cnt in production code
    var c = ~~(t/n);
    return ns.length ? Array(c+1).fill()
                                 .reduce((r,_,i) => r.concat(items2T(ns, t-n*i).map(s => Array(i).fill(n).concat(s))),[])
                     : t % n ? []
                             : [Array(c).fill(n)];
};

var cnt = 0, result;
console.time("combos");
result = items2T([14, 6, 10, 7, 3], 500)
console.timeEnd("combos");
console.log(`${result.length} many unique ways to sum up to 500
and ${cnt} recursive calls are performed`);

Еще один важный момент: если данный массив отсортировать по убыванию, то количество рекурсивных итераций уменьшится (иногда сильно), что позволит нам выжать из этого лимона больше сока. Сравните приведенное выше с приведенным ниже, когда входной массив отсортирован по убыванию.

function items2T([n,...ns],t){cnt++ //remove cnt in production code
    var c = ~~(t/n);
    return ns.length ? Array(c+1).fill()
                                 .reduce((r,_,i) => r.concat(items2T(ns, t-n*i).map(s => Array(i).fill(n).concat(s))),[])
                     : t % n ? []
                             : [Array(c).fill(n)];
};

var cnt = 0, result;
console.time("combos");
result = items2T([14, 10, 7, 6, 3], 500)
console.timeEnd("combos");
console.log(`${result.length} many unique ways to sum up to 500
and ${cnt} recursive calls are performed`);

person Redu    schedule 27.03.2019