查找其总和等于给定目标的整数数组的最高子集 [英] Find the highest subset of an integer array whose sums add up to a given target

问题描述

我试图在一个数组中找到一个值的子集，这些值的总和等于一个给定的数字，然后返回该子集的数组.我需要return数组包含最大可能的最大值.

I am trying to find a subset of values within an array which add up to a given number and return an array of that subset. I need the return array to contain the highest possible largest value.

整数数组将始终按升序排列，但不会始终有一个有效的答案.如果没有有效答案，我需要返回无有效答案"行的字符串.

The integer array will always be in ascending order but there will not always be a valid answer. If there is no valid answer I need to return a string along the lines of 'No valid answer'.

例如:

如果int数组是:[1, 2, 3, 5, 7, 9, 11]，而目标是19-我希望返回数组是[1, 7, 11]. 我不想返回[9, 7, 3]，因为11大于9，并且我不想返回[3, 5, 11]，因为7大于5.

If the int array is: [1, 2, 3, 5, 7, 9, 11] and the target is 19 - I want the return array to be [1, 7, 11]. I would not like to return [9, 7, 3] because 11 is larger than 9, and I would not like to return [3, 5, 11] because 7 is larger than 5.

我假设我将需要在递归函数中使用for循环来获取答案，但一直无法弄清楚该怎么做.

I am assuming that I will need a for loop within a recursive function to get my answer but have been unable to figure out how to do it.

我在Java中发现了该问题的各种变化: https://codereview.stackexchange.com/questions/36214/find-all-subsets-of-int-array-hose-sums-等于给定的目标

I have found variations of the question in Java: https://codereview.stackexchange.com/questions/36214/find-all-subsets-of-an-int-array-whose-sums-equal-a-given-target

我也在JavaScript中找到了一个返回值对的解决方案(尽管这很简单): https://codereview.stackexchange.com/questions/74152/given-an-array-of-integers-return-all-pairs-that-and-upto-to-100

I have also found a solution in JavaScript which returns pairs of values (although this is pretty straight forward): https://codereview.stackexchange.com/questions/74152/given-an-array-of-integers-return-all-pairs-that-add-up-to-100

我当时在想，您需要从数组的最后一个元素开始循环，然后向后循环遍历该数组，以检查是否有两个数字之和作为目标的组合.

I was thinking that you would need to start your loop with the last element of the array and loop backwards through the array to check if there is a combination of 2 numbers whose sum is the target.

如果没有一对，则需要从最高的一对数字开始，这些数字的总和小于目标值，然后遍历数组以查找是否存在组合.

If there is not a pair, you would need to start with the highest pair of numbers whose sum is less that the target and loop though the array to find if there is a combination.

需要继续此操作，直到找到子集或您发现没有有效答案为止.

This operation would need to be continued until the subset is found or you discover that there is no valid answer.

请帮助！

推荐答案

递归的基本模式是:

1. 返回简单案例的已知值.对于此问题，简单的情况是(a)目标为0(解决方案为空数组)和(b)目标为负(失败).
2. 递归并根据答案返回一些计算.对于这个问题，我们查看每个候选值，然后递减一个目标值并递减该值，然后返回一个由递归结果加上当前元素组成的数组.

所以:

// Find subset of a that sums to n.
function subset_sum(n, a) {
  // SIMPLE CASES
  if (n < 0)   return null;       // Nothing adds up to a negative number
  if (n === 0) return [];         // Empty list is the solution for a target of 0

  // RECURSIVE CASE
  a = a.slice();
  while (a.length) {              // Try remaining values
    var v = a.shift();            // Take next value
    var s = subset_sum(n - v, a); // Find solution recursively
    if (s) return s.concat(v);    // If solution, return
  }
}

要强制执行您希望首先偏爱较高值的规则，请将此函数传递一个按降序预排序的值数组.

To enforce the rule that you want to prefer higher values first, pass this function an array of values that is pre-sorted in descending order.

> subset_sum(19, [11, 9, 7, 5, 3, 2, 1])
< [1, 7, 11]

这篇关于查找其总和等于给定目标的整数数组的最高子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！