algorithm - 5つの数字の合計=100

Question

したがって、10個の数字が与えられ、合計が100になるように、それらの中から5個の数字を選択することになっています。

今、私は明らかにプログラムを使用してそれを解決しようとし、5つのループで明白な解決策を得ました。しかし、これを行うための効率的な方法はありますか？

これがMr.Obviousです：

        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

組み合わせて使用​​できます。この質問をチェックしてください: C++ で n 個のアイテムの可能なすべての k 個の組み合わせを作成する

この場合、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();
  }