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

Question

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

var arr = [10, 0, -1, 20, 25, 30];
var sum = 45;
var newArr = [];
console.log('before sorting = ' + arr);

arr.sort(function(a, b) {
  return a - b;
});
console.log('after sorting = ' + arr);

var l = 0;
var arrSize = arr.length - 1;

while (l < arrSize) {

  if (arr[l] + arr[arrSize] === sum) {
    var result = newArr.concat(arr[l], arr[arrSize]);
    console.log(result);
    break;
  } else if (arr[l] + arr[arrSize] > sum) {
    arrSize--;
  } else {
    l++;
  }
}

Массив ввода: [10, 0, -1, 20, 25, 30]

Необходимая сумма: 45

Вывод: [20, 25]

Я пытаюсь набрать

Требуемая сумма: 59

Вывод: [10, -1, 20,30]

Answer 1

Один из вариантов - найти всех возможных подмножеств массива, а затем отфильтровать их по тем, которые суммируются с требуемым значением, а затем определить один (ие) с наименьшей длиной:

const getMinElementsWhichSum = (arr, target) => {
  const subsets = getAllSubsetsOfArr(arr);
  const subsetsWhichSumToTarget = subsets.filter(subset => subset.reduce((a, b) => a + b, 0) === target);
  return subsetsWhichSumToTarget.reduce((a, b) => a.length < b.length ? a : b, { length: Infinity });
};
console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 45));
console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 59));

// /6337430/naiti-vse-vozmozhnye-kombinatsii-podmnozhestv-v-massive
function getAllSubsetsOfArr(array) {
    return new Array(1 << array.length).fill().map(
        (e1,i) => array.filter((e2, j) => i & 1 << j));
}

Answer 2

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

Это означает, что вы разбили бы его на рекурсию, которая пытается найти минимальную длину все меньших массивов с суммой, скорректированной с учетом того, что было удалено. Если ваш массив равен [10, 0, -1, 20, 25, 30] с суммой 59, вы можете думать о самом коротком как о min из:

[10, ... shortest([ 0, -1, 20, 25, 30], 49)
[0,  ... shortest([10, 20, 25, 30], 49), 59)
[-1, ... shortest([10, 0, 20, 25, 30], 60)
... continue recursively

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

Проще показать в коде:

function findMinSum(arr, n){
    if(!arr) return 
    let min 
    for (let i=0; i<arr.length; i++) {

        /* if a number equals the sum, it's obviously
         * the shortest set, just return it
         */
        if (arr[i] == n) return [arr[i]]     
        
        /* recursively call on subset with
         * sum adjusted for removed element 
         */
        let next = findMinSum(arr.slice(i+1), n-arr[i])
        
        /* we only care about next if it's shorter then 
         * the shortest thing we've seen so far
         */
        if (next){
            if(min === undefined || next.length < min.length){
                min = [arr[i], ...next]
            }
        }
    }
    return min && min  /* if we found a match return it, otherwise return undefined */
}

console.log(findMinSum([10, 0, -1, 20, 25, 30], 59).join(', '))
console.log(findMinSum([10, 0, -1, 20, 25, 30], 29).join(', '))
console.log(findMinSum([10, 0, -1, 20, 25, 30], -5)) // undefined when no sum

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

Answer 3

Попробуйте BFS (Breath First Search) алгоритм https://en.wikipedia.org/wiki/Breadth-first_search

Answer 4

Попробуйте,

var arr = [10, 0, -1, 20, 25, 30];
var sum = 29;
var newArr = [];
var sum_expected = 0;
var y = 0;
while (y < arr.length) {
    for (let i = 0; i < arr.length; i++) {
        var subArr = [];
        sum_expected = arr[i];
        if (arr[i] != 0) subArr.push(arr[i]);
        for (let j = 0; j < arr.length; j++) {
            if (i == j)
                continue;
            sum_expected += arr[j];
            if (arr[j] != 0) subArr.push(arr[j]);
            if (sum_expected == sum) {
                var result = arr.filter((el)=>(subArr.indexOf(el) > -1));
                !newArr.length ? newArr = result : result.length < newArr.length ? newArr = result :  1;
                break;
            }
        }
    }
    let x = arr.shift();
    arr.push(x);
    y++;
}
if (newArr.length) {
    console.log(newArr);
} else {
    console.log('Not found');
}