在数组中找到总和等于给定值的最小元素 [英] To find minimum elements in array which has sum equals to given value

问题描述

我正在尝试找出总和等于的数组中的最小元素 给定的输入.我尝试输入的总和很少，但只能找到一个 在第一种情况下配对，而我需要实现的不仅仅是一对.

I am trying to find out the minimum elements in array whose sum equals the given input.I tried for few input sum but was able to find only a pair in first case while I need to implement for more than just a pair.

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]

Input Array : [10, 0, -1, 20, 25, 30]

必填项:45

输出:[20，25]

Output: [20, 25]

我正在尝试

所需总和:59

Required Sum : 59

输出:[10，-1、20、30]

Output: [10, -1, 20, 30]

推荐答案

这可以看作是优化问题，非常适合动态编程.

This can be viewed as an optimization problem which lends itself well to dynamic programming.

这意味着您可以将其分解为一个递归，该递归试图找到越来越小的数组的最小长度，并针对已删除的内容调整总和.如果您的数组是[10, 0, -1, 20, 25, 30]且总和为59，则您可以将最短视为min的

This means you would break it up into a recursion that tries to find the minimum length of increasingly smaller arrays with the sum adjusted for what's been removed. If your array is [10, 0, -1, 20, 25, 30] with a sum of 59 you can think of shortest as the min of:

[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

每次递归时，数组变短，直到剩下一个元素为止.然后问题是该元素是否等于所有减法后剩余的数字.

with each recursion, the array gets shorter until you are left with one element. Then the question is whether that element equals the number left over after all the subtractions.

更容易在代码中显示:

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

这在计算上仍然非常昂贵，但比查找所有子集和总和要快得多.

This is still pretty computationally expensive but it should be much faster than finding all the subsets and sums.

这篇关于在数组中找到总和等于给定值的最小元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！