Целое решение линейного уравнения с вещественными коэффициентами

Question

Я пытаюсь выяснить, есть ли способ решить уравнение в виде

сумму (w_i * x_i) = ш^Т х = S

(https://chart.googleapis.com/chart?cht=tx&chl= \ sum_ {я% 3D0}^{п}% 20w_i% 20x_i% 20% 3D% 20w^Tx% 20% 3D% 20s)

где коэффициенты w_i реальны, и неизвестные x_i являются целыми числами, а результат суммы s вещественный.

Мне не интересно знать все возможные решения, но только те, которые обеспечивают меньшие значения решений, а затем исследуют, какой из них имеет смысл. У меня есть ограничения на неизвестность, что они не превысят определенного предела (например, 100).

Это тривиальное решение для выполнения вложенных циклов для каждого x_i и сохранения решения каждый раз, когда сумма равна желаемому результату. Однако это очень дорого и занимает слишком много времени, когда число unknows увеличивается (Неизвестный может находиться в диапазоне от 100 до 1000).

Я попытался понять диофантово уравнение и его расширение для системы линейных уравнений. В этом случае у меня есть одно уравнение с n неизвестными

Любые идеи по оптимизации решения этой проблемы?

Answer 1

Короткий ответ - нет. Например, рассмотрим $ n = 1 $ и $ w_0 = w_1 = 1 $ и $ s = 0 $. Вы получаете $ x_0 + x_1 = 0 $, для которого любое целое число $ x_0 $ в порядке, если $ x_1 = -x_0 $. У вас есть одно уравнение с $ n $ unknowns. Тот факт, что $ w_i $ вещественные и $ x_i $ - целые числа, может уменьшить количество решений, но это не так, как правило,