Давайте начнем с набора интересных наблюдений. Как отметили многие другие, цель состоит в том, чтобы найти некоторую линейную комбинацию 5x + 7y + 12z = b - a с целыми коэффициентами, такую, что | x | + | y | + | z | сводится к минимуму Но между этими тремя числами есть несколько очень интересных связей, которые мы можем использовать:
- Если у нас когда-либо будет комбинация 5x + 7y + 12z, где x и y оба положительные или оба отрицательные, мы можем отменить некоторое количество x и y, чтобы добавить эквивалентное число 12. Другими словами, ни одно оптимальное решение не имеет одинакового знака на x и y, потому что мы всегда можем сделать это решение лучше.
- Если у нас когда-либо будет комбинация 5x + 7y + 12z, где y и z имеют противоположные знаки, мы всегда можем удалить 7 и 12 и добавить 5 соответствующих знаков, чтобы получить лучшее решение. Аналогично, если x и z имеют противоположные знаки, мы всегда можем удалить 5 и 12 и добавить 7 соответствующего знака. Это означает, что нам никогда не нужно рассматривать какое-либо решение, где z имеет тот же знак, что и x или y, потому что это означает, что должно быть лучшее решение.
Давайте подумаем о том, что (1) и (2) сообщают нам все вместе. (1) говорит, что знаки x и y не могут быть одинаковыми, так как мы всегда можем добиться большего. (2) говорит, что если x и z имеют противоположные знаки или если y и z имеют противоположные знаки, мы всегда можем добиться большего. В совокупности это означает, что
Лемма : По крайней мере один из x, y или z должен быть равен нулю в оптимальном решении.
Чтобы увидеть это, если все три отличны от нуля, если x и y имеют один и тот же знак, мы можем явно улучшить решение, заменив их на 12. В противном случае x и y имеют противоположные знаки. Таким образом, если x и z имеют разные знаки, с помощью (2) мы можем заменить их на меньшее число 7, в противном случае y и z имеют разные знаки, а с помощью (2) мы можем заменить их на меньшее число 5.
Хорошо, это выглядит действительно здорово! Это означает, что нам просто нужно решить эти три целочисленных уравнения и найти, какое из них имеет наименьшую сумму коэффициентов:
- 5x + 7y = b - a
- 5x + 12z = b - a
- 7y + 12z = b - a
К счастью, по тождеству Безу , поскольку gcd (5, 7) = gcd (5, 12) = gcd (7, 12) = 1, все эти системы уравнений имеют решение для любого значение b - a.
Теперь посмотрим, как решить каждое из этих уравнений. К счастью, мы можем использовать несколько милых трюков, чтобы значительно сократить пространство поиска. Например, для 5x + 7y = b - a значение x не может быть вне [-6, +6], так как если бы мы могли просто заменить семь из 5 на пять 7. Это означает, что мы можем решить вышеприведенное уравнение, выполнив следующее:
Для x = от -6 до +6 посмотрите, имеет ли 5x + 7y = b - a целочисленное решение, вычислив (b - a) - 5x и посмотрев, делится ли оно на семь. Если это так, то количество шагов, необходимых для решения проблемы, определяется как | x | + | ((б - а) - 5х) / 7 |.
Мы можем использовать аналогичные приемы для решения последних двух уравнений - для второго уравнения x находится в диапазоне от -11 до +11, а для третьего y также в диапазоне от -11 до +11. Затем мы можем просто взять лучший ответ из всех трех уравнений, чтобы увидеть, каков ответ.
Вот некоторый псевдокод для записи наименьшего числа возможных шагов. Это может быть легко изменено, чтобы возвратить эти шаги, просто записав, какое из решений было использовано, а затем развернув его в полный путь:
Let best = infinity
# Solve 5x + 7y = b - a
for x = -6 to +6:
if ((b - a) - 5 * x) mod 7 = 0:
best = min(best, |x| + |((b - a) - 5 * x) / 7|)
# Solve 5x + 12y = b - a
for x = -11 to +11:
if ((b - a) - 5 * x) mod 12 = 0:
best = min(best, |x| + |((b - a) - 5 * x) / 12|)
# Solve 7x + 12y = b - a
for x = -11 to +11:
if ((b - a) - 7 * x) mod 12 = 0:
best = min(best, |x| + |((b - a) - 7 * x) / 12|)
return best;
Этот алгоритм удивительно быстр - он выполняется за O (1) времени, потому что число итераций, необходимое для решения каждой из трех линейных систем, является постоянным (не более 23). Для хранения возможных значений требуется только O (1) памяти, и я думаю, что на практике это, вероятно, самый быстрый алгоритм, который вы сможете написать.
Надеюсь, это поможет!