algorithm - 5 个数字的总和 = 100

Question

所以，给你 10 个数字，你应该从中选择 5 个数字，这样总和就是 100。

现在，我显然尝试使用程序来解决它，并通过五个循环得到了明显的解决方案。但我只是想知道有没有有效的方法来做到这一点？

这是明显的先生：

        static void Main(string[] args)
        {
            int[] a = { 2, 6, 10, 14, 18, 22, 26, 30, 34, 38 };
            for (int f = 0; f < a.Length - 4; f++)
            {
                for (int s = f+1; s < a.Length - 3; s++)
                {
                    for (int t = s+1; t < a.Length - 2; t++)
                    {
                        for (int fr = t + 1; fr < a.Length - 1; fr++)
                        {
                            for (int ft = fr + 1; ft < a.Length; ft++)
                            {
                                int sum = a[f] + a[s] + a[t] + a[fr] + a[ft];
                                Console.WriteLine(sum);
                                if (sum == 100)
                                {
                                    Console.WriteLine("---------------------------------------");
                                    Console.WriteLine(a[f]);
                                    Console.WriteLine(a[s]);
                                    Console.WriteLine(a[t]);
                                    Console.WriteLine(a[fr]);
                                    Console.WriteLine(a[ft]);
                                    Console.WriteLine("---------------------------------------");
                                }
                            }

                        }
                    }
                }
            }
            Console.ReadLine();
        }

Answer 1

您可以使用组合。看看这个问题： create all possible k combination of n items in C++

在这种情况下，您有 n 个数字和 k 个数字索引可供选择。

这应该会减少迭代次数。

Answer 2

这里有一些优化的想法：

• 如果所有数字都是正数，您可以跳过内部循环，总和已经 >= 100
• 您可以通过计算每个循环中的部分和来减少计算（运行内部循环时外部循环的值不会改变）。

• 只计算a.Length一次并存储它，因为这个值永远不会改变

  static void Main(string[] args)
  {
      int[] a = { 2, 6, 10, 14, 18, 22, 26, 30, 34, 38 };
      int lenA=a.Length;
      int alenMinus4=lenA-4,
      int alenMinus3=lenA-3,
      int alenMinus2=lenA-2,
      int alenMinus1=lenA-1,
  
      for (int f = 0; f < alenMinus4; f++)
      {   int sum1=a[f];
          if(sum1>100)
          { f=alenMinus4;
          }
          else
          {   for (int s = f+1; s < alenMinus3; s++)
              {   int sum2=sum1+ a[s];
                  if(sum2>100)
                  { s=alenMinus3;
                  }
                  else
                  {   for (int t = s+1; t < alenMinus2; t++)
                      {   int sum3=sum2+ a[t];
                          if(sum3>100)
                          { t=alenMinus2;
                          }
                          else
                          {   for (int fr = t + 1; fr < alenMinus1; fr++)
                              {   int sum4=sum3+ a[fr];
                                  if(sum4>100)
                                  { fr=alenMinus1;
                                  }
                                  else
                                  {  for (int ft = fr + 1; ft < lenA; ft++)
                                      {   int sum = sum4 + a[ft];
                                          Console.WriteLine(sum);
                                          if (sum == 100)
                                          {   Console.WriteLine("---------------------------------------");       
                                              Console.WriteLine(a[f]);
                                              Console.WriteLine(a[s]);
                                              Console.WriteLine(a[t]);
                                              Console.WriteLine(a[fr]);
                                              Console.WriteLine(a[ft]);
                                              Console.WriteLine("---------------------------------------");
      }   }   }   }   }   }   }   }   }   }
      Console.ReadLine();
  }