如何有效地生成总和在指定范围内的所有组合（在所有深度）

5 回答

• 0

  将主要呼叫切换到：

  GenerateCombinationsHelper2(new List<int[]>(), 13, 17, 0, maxCounts, new int[3], values);
  

  然后添加以下代码：

  private void GenerateCombinationsHelper2(List<int[]> results, int min, int max, int index, int[] maxValues, int[] currentCombo, int[] values)
  {
      int max_count = Math.Min((int)Math.Ceiling((double)max / values[index]), maxValues[index]);
  
      for(int count = 0; count <= max_count; count++)
      {
          currentCombo[index] = count;
          if(index < currentCombo.Length - 1)
          {
              GenerateCombinationsHelper2(results, min, max, index + 1, maxValues, currentCombo, values);
          }
          else
          {
              int sum = Sum(currentCombo, values);
              if(sum >= min && sum <= max)
              {
                  int[] copy = new int[currentCombo.Length];
                  Array.Copy(currentCombo, copy, copy.Length);
                  results.Add(copy);
              }
          }
      }
  }
  
  private static int Sum(int[] combo, int[] values)
  {
      int sum = 0;
      for(int i = 0; i < combo.Length; i++)
      {
          sum += combo[i] * values[i];
      }
      return sum;
  }
  

  它返回5个有效答案 .

  回复于 2024-04-29T10:00:59+08:00
• 0

  这类问题的一般趋势是，相对较少的值会出现，但每个值都会显示很多次 . 因此，您首先要创建一个数据结构，该数据结构可以有效地描述将添加到所需值的组合，然后才能找出所有这样做的组合 . （如果您知道术语“动态编程”，那正是我所描述的方法 . ）

  C＃术语中明显的数据结构是Hashtable，其键是组合加起来的总数，其值是列出最后元素位置的数组，这些元素可以组合使用，可以累加到特定总数 .

  你如何 Build 这种数据结构？

  首先，您从一个Hashtable开始，该Hashtable包含总数0作为键，空数组作为值 . 然后，对于数组的每个元素，您可以创建一个可以从之前的总计中获得的新总计列表，并将元素的位置附加到它们的每个值（如果需要，可以插入一个新的值） . 当您浏览完所有元素后，您就拥有了自己的数据结构 .

  现在，您可以仅针对所需范围内的总计搜索该数据结构 . 对于每个这样的总数，您可以编写一个递归程序，它将遍历您的数据结构以生成组合 . 这个步骤确实可以有一个组合爆炸，但好的是产生的 EVERY 组合实际上是你最后答案的组合 . 因此，如果这个阶段需要很长时间，那是因为你有很多最终答案！

  回复于 2024-04-29T10:00:59+08:00
• 0

  试试这个算法

  int arr[] = {1,1,1,12,12,16}
  for(int i = 0;i<2^arr.Length;i++)
  {
  int[] arrBin = BinaryFormat(i); // binary format i
  for(int j = 0;j<arrBin.Length;j++)
    if (arrBin[j] == 1)
       Console.Write("{0} ", arr[j]);
  Console.WriteLine();
  }
  

  回复于 2024-04-29T10:00:59+08:00
• 1

  这与恰好是NP-complete的subset sum problem非常相似 .

  维基百科说以下关于NP完全问题：

  尽管可以快速验证对此类问题的任何给定解决方案，但首先没有已知的有效方法来定位解决方案;实际上，NP完全问题最显着的特征是没有快速解决它们的问题 . 也就是说，随着问题的大小增加，使用任何当前已知算法解决问题所需的时间增加得非常快 . 这意味着，使用当今可用的任何数量的计算能力，解决许多这些问题的中等尺寸版本所需的时间可以轻松达到数十亿或数万亿年 . 因此，确定是否有可能快速解决这些问题，称为P与NP问题今天计算机科学中尚未解决的主要问题之一 .

  如果确实有一种方法可以解决这个问题，除了通过powerset强制执行并找到总和达到给定范围内的值的所有子集，那么我会非常有兴趣听到它 .

  回复于 2024-04-29T10:00:59+08:00
• 1

  另一个实现的想法：

  从数字列表中创建堆栈列表，每个堆栈代表一个出现在列表中的数字，并且这个数字被推入堆栈的次数与数字列表中出现的数量相同 . 更重要的是，此列表已排序 .

  我们的想法是，您遍历堆栈列表，在每个堆栈中，如果它没有超过最大值，则一次弹出一个数字并调用该函数，并执行跳过当前堆栈的额外调用 .

  该算法减少了许多冗余计算，例如在添加此值超过最大值时尝试添加具有相同值的不同元素 .

  我能够用这个算法解决相当大的问题（50个数字和更多），这取决于最小值和最大值，显然当间隔非常大时，组合的数量可能很大 .

  这是代码：

  static void GenerateLimitedCombinations(List<int> intList, int minValue, int maxValue)
  {
      intList.Sort();
      List<Stack<int>> StackList = new List<Stack<int>>();
      Stack<int> NewStack = new Stack<int>();
      NewStack.Push(intList[0]);
      StackList.Add(NewStack);
  
      for (int i = 1; i < intList.count; i++)
      {
          if (intList[i - 1] == intList[i])
              StackList[StackList.count - 1].Push(intList[i]);
          else
          {
              NewStack = new Stack<int>();
              NewStack.Push(intList[i]);
              StackList.Add(NewStack);
          }
      }
  
      GenerateLimitedCombinations(StackList, minValue, maxValue, 0, new List<int>(), 0);
  }
  
  static void GenerateLimitedCombinations(List<Stack<int>> stackList, int minValue, int maxValue, int currentStack, List<int> currentCombination, int currentSum)
  {
      if (currentStack == stackList.count)
      {
          if (currentSum >= minValue)
          {
              foreach (int tempInt in CurrentCombination)
              {
                  Console.Write(tempInt + " ");
              }
              Console.WriteLine(;
          }
      }
  
      else
      {
          int TempSum = currentSum;
          List<int> NewCombination = new List<int>(currentCombination);
          Stack<int> UndoStack = new Stack<int>();
  
          while (stackList[currentStack].Count != 0 && stackList[currentStack].Peek() + TempSum <= maxValue)
          {
              int AddedValue = stackList[currentStack].Pop();
              UndoStack.Push(AddedValue);
              NewCombination.Add(AddedValue);
              TempSum += AddedValue;
              GenerateLimitedCombinations(stackList, minValue, maxValue, currentStack + 1, new List<int>(NewCombination), TempSum);
          }
  
          while (UndoStack.Count != 0)
          {
              stackList[currentStack].Push(UndoStack.Pop());
          }
  
          GenerateLimitedCombinations(stackList, minValue, maxValue, currentStack + 1, currentCombination, currentSum);
      }
  }
  

  这是一个测试程序：

  static void Main(string[] args)
  {
      Random Rnd = new Random();
      List<int> IntList = new List<int>();
      int NumberOfInts = 10, MinValue = 19, MaxValue 21;
  
      for (int i = 0; i < NumberOfInts; i++) { IntList.Add(Rnd.Next(1, 10));
      for (int i = 0; i < NumberOfInts; i++) { Console.Write(IntList[i] + " "); } Console.WriteLine(); Console.WriteLine();
  
      GenerateLimitedCombinations(IntList, MinValue, MaxValue);
      Console.ReadKey();
  }
  

  回复于 2024-04-29T10:00:59+08:00