0

我有一个 numberArray。它包含整数 - 在特定范围内随机化。我想得到一个特定的总和，但不是针对 numberArray 中的所有内容，更多的是尝试对 numberArray 中不同数量的数字（总共 5 个）求和，看看它是否会得到所需的特定总数。如果没有，它会随机化另一个数字来接管 numberArray 中的一个数字。

最简单的方法是什么？

做很多

    if (numberArray[1] + numberArray[2] == specificNumber) 
    {
    }
    if (numberArray[1] + numberArray[3] == specificNumber)
    {
    }

etc. etc. etc. 的代码行数太多，似乎有更简单的代码。现在我数组中只有5个不同的数字，所以它仍然可以忍受，但如果数字的数量更高......

4

3 回答 3

0

我会做类似以下的事情：

  • 洗牌数组
  • 从数组中获取随机数量的数字
  • 总结他们
  • 如果总和不是您想要的总和，请重复
于 2013-08-09T15:28:53.443 回答
0

嗯，当得出“结论”或“无结论”时，不确定最后你想做什么，但你可以从你的一组数字中生成一个幂集，然后为每个子集添加其中的所有数字以查看如果你得到你想要的金额。

（这将是一种“蛮力”方法，如果您有很多数字，可能会很慢。）

可能对如何创建幂集有用： 计算一组数字的所有子集

于 2013-08-09T22:39:52.570 回答
0

像这样阅读您的问题：对于您的随机整数数组，找到一组（或所有）具有给定总和的整数。

这是一个 NP 完全问题 - 即没有已知的算法可以有效地解决它。

已知最快的方法相当复杂，因此我们将采用一个简单的解决方案 - 如果您不是在每一帧上都这样做或者输入集很大，那么应该就足够了。

这也应该适用于输入集中的 0 或负值。

// The sum we're looking for:
var requiredSum:int              = 8;
// Our input set:
var numberArray:Array            = [1, 2, 3, 4, 5, 2, 3];
// Results will be stored here:
var resultSets:Array             = [];

// Go through all possible subset sizes.
// This allows subset sizes all the way up to the size of 
// the input set (numberArray.length).
// You can modify it to a fixed value (say, 5), of course:
for (var subsetSize:int = 1; subsetSize <= numberArray.length; subsetSize++)
{
   // We'll use the same array for all our attempts of this size:
   var subset:Array = new Array(subsetSize);
   findSum(numberArray, subset, 0, 0);
}

// Output results:
for (var i:int = 0; i < resultSets.length; i++)
{
    trace(resultSets[i].join("+"));
}

// numberArray : Our input set
// subset      : The set we're currently filling
// setIndex    : The position we're at in numberArray
// subsetIndex : The position we're at in the set we're filling
function findSum(numberArray:Array, subset:Array, setIndex:int, 
                 subsetIndex:int):void
{
   // Try every value from the input set starting from our current position, 
   // and insert the value at the current subset index:
   for (var index:int = setIndex ; index < numberArray.length; index++)
   {
      subset[subsetIndex] = numberArray[index];

      // Have we filled the subset?
      if (subsetIndex == subset.length - 1)
      {
         var sum:int = 0;
         for (var i:int = 0; i < subset.length; i++)
         {
            sum += subset[i];
         }

         if (sum == requiredSum)
         {
            // Clone the array before adding it to our results, 
            // since we'll be modifying it if we find more:
            resultSets.push(subset.concat());
         }
      }
      else
      {
         // Recursion takes care of combining our subset so far
         // with every possible value for the remaining subset indices:
         findSum(numberArray, subset, index + 1, subsetIndex + 1);
      }
   }
}

上述代码中使用的值的输出：

3+5
5+3
1+2+5
1+3+4
1+4+3
1+5+2
2+3+3
2+4+2
3+2+3
1+2+3+2
1+2+2+3

如果我们只需要知道是否存在总和，则不需要结果集——我们只返回真/假，并在找到总和时完全退出递归算法：

var requiredSum:int   = 8;
var numberArray:Array = [1, 2, 3, 4, 5, 2, 3];

// Go through all possible subset sizes:
for (var subsetSize:int = 1; subsetSize <= numberArray.length; subsetSize++)
{
   // We'll use the same array for all our attempts of this size:
   var subset:Array = new Array(subsetSize);
   if (findSum(numberArray, subset, 0, 0))
   {
      trace("Found our sum!");
      // If we found our sum, no need to look for more sets:
      break;
   }
}

// numberArray : Our input set
// subset      : The set we're currently filling
// setIndex    : The position we're at in numberArray
// subsetIndex : The position we're at in the set we're filling
// RETURNS     : True if the required sum was found, otherwise false.
function findSum(numberArray:Array, subset:Array, setIndex:int, 
                 subsetIndex:int):Boolean
{
   // Try every value from the input set starting from our current position, 
   // and insert the value at the current subset index:
   for (var index:int = setIndex ; index < numberArray.length; index++)
   {
      subset[subsetIndex] = numberArray[index];

      // Have we filled the subset?
      if (subsetIndex == subset.length - 1)
      {
         var sum:int = 0;
         for (var i:int = 0; i < subset.length; i++)
         {
            sum += subset[i];
         }

         // Return true if we found our sum, false if not:
         return sum == requiredSum;
      }
      else
      {
         if (findSum(numberArray, subset, index + 1, subsetIndex + 1))
         {
            // If the "inner" findSum found a sum, we're done, so return
            // - otherwise stay in the loop and keep looking:
            return true;
         }
      }
   }
   // We found no subset with our required sum this time around:
   return false;
}

ETA：这是如何工作的......如前所述，这是一个简单的解决方案 - 换句话说，我们只是检查 的每个排列numberArray，对每个排列求和，并检查它是否是我们想要的总和。

最复杂的部分是进行所有排列。这段代码的方式是通过递归——即，findSum()函数填充一个槽然后调用自己来填充下一个槽，直到所有槽都被填满并且它可以检查总和。我们将在numberArray这里使用 [1, 5, 4, 2] 作为示例：

  1. 在一个循环中遍历所有子集大小 - 即，首先制作所有 [a]，然后是所有 [a,b]、[a,b,c]、[a,b,c,d]... 等等。
  2. 对于每个子集大小：
    1. 填充1子集的插槽...
    2. ... numberArray 的每个值 - [ 1 , ?, ?], [5, ?, ?], [4, ?, ?] ...
    3. 如果子集中的所有槽都已填满，请检查总和是否匹配并跳过步骤 4。
    4. （递归）调用findSum：
      1. 填充2子集的插槽...
      2. ... numberArray 的每个剩余值 - [1, 5 , ?], [1, 4, ?], [1, 2, ?]
      3. 如果子集中的所有槽都已填满，请检查总和是否匹配并跳过步骤 4。
      4. （递归）调用findSum：
        1. 3子集的填充槽
        2. ... numberArray 的每个剩余值 - [1, 5, 4 ], [1, 5, 2]
        3. 如果子集中的所有槽都已填满，请检查总和是否匹配并跳过步骤 4。
        4. （递归）调用findSum（这会“永远”进行，或者直到所有插槽都被填满并且我们“跳过第 4 步”）
        5. 转至 2.4.4.1。尝试下一个值 slot 3。
      5. 转到 2.4.1 尝试下一个值 slot 2。
    5. 转到 2.1 尝试下一个值 slot 1。

这样，我们遍历大小为 1、2、3、4 的每个排列...

这里可以进行更多优化，因为代码从不检查输入集中实际上是否有足够的值来填充剩余的插槽——即它会执行一些循环并且findSum()不需要对其进行调用。然而，这只是效率问题 - 结果仍然是正确的。

于 2013-08-10T01:34:10.410 回答