与えられた方程式
2(p 1 ) + 3(p 2 ) + 7(p 3 ) >= 257のように
p 1、p 2、p 3のすべての可能な組み合わせを見つける必要があります。これにより 、上記のステートメントが真になり、結果の合計 (方程式の左側) がすべての x nが既知の場合に最小になります。
のような一般的なケースのアルゴリズムを調べてみました
(x 1 )(p 1 ) + (x 2 )(p 2 ) + (x 3 )(p 4 ) + ... + (x n )(p n ) >= ターゲット
そして、ナップザック問題とサブセット和アルゴリズムの解決策に出くわしましたが、それらはこの問題とまったく同じではありませんでした。
p nの下限値を持つ Python 3.x のアルゴリズムを使用する前に試してみましたが、それでも O(とんでもない) 時間の複雑さで実行されます。
明らかに、ここでの数はすべて自然数であり、そうでなければ無限の解が存在します。
Pi が >= 0 である必要があるかどうかに応じて、2 つの可能なアプローチを見ることができます。Pi >= 0 の場合はより賢明なので、最初に検討します。
これを、方程式に沿って左から右に作業する動的計画法として扱います。コメントのより大きな方程式を見て、まず p0 からの寄与のリストを作成します: 0、5、10、15... 190384760、そしてそれらの横にそれらを生成する p0 の値: 0、1、2、 ... 190384760/5.
次に、この表を使用して、最初の 2 つを組み合わせて 5p0 + 7p1 の値を計算します: 0、5、7、10、12、14....そして、それらを生成するために必要な p1 の値を保持します。
右から左に作業すると、p0..p8 の正の整数の組み合わせによって作成できる 190384755 をわずかに超える値のテーブルになります。明らかに、最大のもの>= 190384755のみを気にします。p8の寄与のすべての可能な値を考慮し、これらを190384755から減算し、表でp0..p7を調べて、これらのどれが可能かを確認します。これにより、p8 のすべての可能な値が得られ、これらのそれぞれに対してプロセスを再帰的に繰り返して、p7 のすべての可能な値を出力することができます。 190384755 を超えています。これは、サブセット和の疑似多項式アルゴリズムに非常に似ています。
Pi が < 0 になる可能性がある場合、達成可能な値はすべて Pi の gcd の倍数であり、すべてが整数である可能性が非常に高く、これに対する解は無数にあります。これが本当に必要な場合は、http://en.wikipedia.org/wiki/Extended_Euclidean_algorithmについて読むことから始めることができます。