3

1、2、3 のような数字のリストがあり、合計が 5 のような特定の数字になるすべての組み合わせパターンを見つけたいと考えています。例:

Sum=5
Numbers:1,2,3
Patterns:

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
2 3

合計を超えない限り、数字を繰り返すことができます。これをプログラムするのに最適な方法はどれですか?

4

7 に答える 7

8

これは、変更作成の問題を少し修正したものです。この問題に関する多くの論文を見つけることができるはずであり、動的プログラミングのソリューションには 20 行以上のコードは必要ありません。

http://en.wikipedia.org/wiki/Change-making_problem

于 2009-09-29T00:50:39.147 に答える
2

これも役立つかもしれません：動的計画法：組み合わせ和問題

于 2009-09-29T01:26:37.070 に答える
2

この問題は、「二重に制限された整数パーティション」として知られています。合計が 5 になることが「許可された」数がセット V からのものである場合、それは「乗算制限整数分割」として知られています。Riha と James による論文があります。その論文を読んで、そのアルゴリズムを実装する必要があります。その方法を理解すると、特定の問題に固有の最適化を実装できるようになります。

于 2012-09-25T17:39:05.977 に答える
2

これらは番号のパーティションと呼ばれ、あなたの問題は、パーティションで使用できる番号の制約を課しているようです。

于 2009-09-29T05:18:57.117 に答える
0 
    public static List<List<string>> Partition(int n, int max, string prefix)
    {

        if (n == 0)
        {
            _results.Add(prefix.Split(new char[] { ',' }).ToList());
        }

        for (int i = Math.Min(max, n); i >= 1; i--)
        {
            Partition(n - i, i, prefix + "," + i);
        }

        return _results;
    }
于 2010-12-30T13:29:23.557 に答える
0

最初に最大数から始めて再帰的に行います。次に、毎回最高レベルから始めて、数字と同じ数のレベルに入ります。累積レベルが自分の値を超えるとすぐに、次の番号にドロップダウンします。それでも大きすぎる (または小さすぎる) 場合は、すぐに 1 つのレベルに戻り、THAT を次の数字に減らしてから、もう一度一番上から始まる次の深いレベルに減らします..

于 2009-09-29T00:46:36.153 に答える
-1

次のコードを使用できます..必要に応じて正確な答えが得られます..

void print(int n, int * a)

{
   int i ; 

   for (i = 0; i <= n; i++) 

   {

  printf("%d", a[i]); 

  }

 printf("\n"); 

}


void integerPartition(int n, int * a, int level)

{

   int first; 

  int i; 

  if (n < 1) 

 return ;    

 a[level] = n;

  print(level, a);

  first = (level == 0) ? 1 : a[level-1];

  for(i = first; i <= n / 2; i++)

   {

       a[level] = i; 

       integerPartition(n - i, a, level + 1);

   }

}

int main()

  {

   int n = 10;     

   int * a = (int * ) malloc(sizeof(int) * n); 

   integerPartition (n, a, 0); 

   return(0);

}
于 2013-07-10T12:38:27.420 に答える