問題タブ [diophantine]

線形ディオファントス方程式を解くために、Python でアルゴリズムをコーディングしようとしています。

紙でテストしたのでアルゴリズムは正しいと思いますが、実行すると奇妙な値が返されます。

私のコード:

7 つの変数と 3 つの補助変数を使用します。ペンと紙でテストした後、次の値を使用します。

私は得る

ただし、実行すると：

戻り値:

整数因数分解の特定のケースに対する効率的な解決策を探しています。効率的とはO(2^n)、現在持っている よりもかなり高速であることを意味します (n は、完了後の配列内の要素の数を表します)。

次の配列が[4, 5, 11]あり、「目標」が 84 であるとします。

を満たすことが可能かどうかを知りたいのですが4*a + 5*b + 11*c = 84、

次の制約が与えられます。

• 0 <= a <= 3
• 0 <= b <= 2
• 0 <= c <= 1

解決策が見つからない場合は、配列に整数を追加します。たとえば、15 としましょう。[4, 5, 11, 15]

ここで、何かが満たされているかどうかを知りたい4*a + 5*b + 11*c + 15*d = 84

とすれば

• 0 <= a <= 4
• 0 <= b <= 3
• 0 <= c <= 2
• 0 <= 日 <= 1

...そして、解決策が見つかるまで、または n 回までプロセスを繰り返します。問題の反復的な特性を利用して、効率的な解決策を見つけることができるかどうか疑問に思っていました。

• 「目標」は変わらない
• 整数は昇順です
• a、b、c... の最大制約は、新しい要素を追加するたびに 1 ずつ増加します
• 繰り返しのたびに式に何かが追加されますが、何も変更されません (制約以外)

何か案は？