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 ずつ増加します
  • 繰り返しのたびに式に何かが追加されますが、何も変更されません (制約以外)

何か案は？

4

1 に答える 1

3

まず用語が間違っています。これは整数因数分解ではなく、いくつかの制約が追加された多くの変数を持つ線形ディオファントス方程式です。

制約がなければ、それは簡単な作業です。見つけGCD(list of coefficients)て、それが自由期間を分割する場合-解決策がありますが、そうでない場合はそうではありません.

制約があれば最初のステップになる可能性がありますが、ここで解決策があることがわかった場合、それらは制約を満たさない可能性があります。

簡単な（多項式の解法）が見当たらないので、これに対処する方法を次に示します。あなたが持っているここに画像の説明を入力

私は中間アプローチで満たすことを使用し、2 つの部分に制約のある方程式を分割します。

パート1はここに画像の説明を入力、

パート2はここに画像の説明を入力

ここで、両方の部分で実行される計算の数がほぼ同じになるように (制約を考慮して) 分割します。

ここで、最初の部分を繰り返し処理し、すべてを辞書に格納します。次に、2 番目のものを反復処理し、答えが辞書に存在するかどうかを確認します。はいの場合、解決策が見つかりました。

これは指数を 2 で割りますが、メモリが必要です。

この数学の答えは、誰かが私が見つけることができなかったより良いアプローチを考え出すのに役立つかもしれません.

于 2016-01-08T00:26:23.187 に答える