整数解

Question

私は形でワット

合計（w_i * X_I）= を方程式を解くためにどのような方法がある場合は、把握しようとしています^T X = S

（https://chart.googleapis.com/chart?cht=tx&chl= \ sum_ {I％3D0}^{N}％20w_i％20x_i％20％3D％20ワット^のTx％20％3次元％の20S）

係数は実数であるw_i

、及び未知数x_iは整数であり、和結果sは実数である。

私はすべての可能な解決策を知ることに関心がありませんが、より小さい解決策の値を提供し、どれが有意義であるかを調べるものだけに興味があります。私は、特定の制限（例えば100）を超えないことを未知のものに制限しています。

各x_iのネストされたfor-loopsを実行し、合計が目的の結果と等しくなるたびにソリューションを保存するという、これに対する簡単な解決策です。しかし、これは非常にコストがかかり、未知数が増える（Unknownが100から1000までの範囲である）場合には時間がかかりすぎる。

ディオファンタス方程式とその拡張を線形方程式系で理解しようとしました。この場合、私はn個の未知数を持つ1つの方程式を持っています

どのようにしてこの問題の解を最適化することができますか？

Answer 1

短い答えはノーです。たとえば、$ n = 1 $と$ w_0 = w_1 = 1 $と$ s = 0 $を考えてみましょう。 $ x_1 = -x_0 $であれば、$ x_0 + x_1 = 0 $が得られます。整数$ x_0 $はOKです。あなたが持っているのは、$ n $の未知数を持つ単一の方程式です。 $ w_i $が実数で$ x_i $が整数であるという事実は、解の数を減らすかもしれませんが、一般的にそうではありません。