1

方程式があります: 1a + 2b + 3c + 4d ... + 9i = 9

制約: 1 <= a + b + c + ... + i <= 10 4

ここで、a、b、..、iは非負の整数で、各整数には特定の範囲があります。

例: 1 <= a <= 5、2 <= b <= 3など。

これらの変数の異なる値のセットの数、または単にその方程式を解く方法の数を見つける必要があります。

これを解決する再帰的な方法がありますが、それは非常に遅いです。与えられた制約の下でこれを効率的に解決する方法を考えることができません。

4

3 に答える 3

2

考えてみれば、解決策は実際には非常に限られています。

すべての数値は負ではないため、次のようになります。

1a + 2b + 3c + 4d ... + 9i = 9

これは、次のことを意味します。

0 <= a <= 9
0 <= b <= 4
0 <= c <= 3
0 <= d <= 2
0 <= e <= 1
0 <= f <= 1
0 <= g <= 1
0 <= h <= 1
0 <= i <= 1

つまり、10*5*4*3*2*2*2*2*2 = 19200考慮すべきケースのみがあります。

これらのケースを反復して、他の制約を満たしているものと、他の制約を満たしているものを見つけることができます。

1a + 2b + 3c + 4d ... + 9i = 9

ヒント: からiまでの値を与えることから始めますa。このようにして、たとえば、iまたはの値が高いと、小さい数値の可能な値の範囲が即座に縮小されます。h

計算する前に、必ずMSaltersのメソッドを適用してください。この場合、問題が簡単すぎるため必要ありませんが、一般的には非常に役立ちます.

于 2012-08-07T10:42:59.650 に答える
1

別の解決策は、1a + 2b + 3c + 4d ... + 9i = 1（簡単な）解き、1a + 2b + 3c + 4d ... + 9i = N+1与えられたの解をすべて見つけることです1a + 2b + 3c + 4d ... + 9i = N。それは基本的にa => a+1またはa=>a-1, b=>b+1またはb=>b-1, c=>c+1などです。

これは非常に再帰的ですが、N = 9に到達するのに8回の反復しか必要とせず、各反復で9つの変数をインクリメントまたはデクリメントするだけです。

于 2012-08-07T10:56:21.770 に答える
1

基本的に、範囲が制限されている変数を置き換えたいと思うので a' = a+1, 0 <= a' <= 4、b' = b+2, 0 <= b' <= 1. ゼロから始めると、計算が簡単になります。また、式を のように書き換えることもできます1a' + 2b' + ... + 9i = 4。すべての用語が非負であるため、これにより検索スペースが大幅に制限されます。たとえば、まではすべて 0 でなければならないことを意味eしiます`1a' + 2b' + 3c + 4d = 4。

于 2012-08-07T10:43:48.380 に答える