У меня есть следующая проблема:
Учитывая набор сумм переменных, таких как {a + b, b + c, c + d, a + a + d, b}, найдите положительные целые значения для переменных, такие что все суммы различны, а самая высокая сумма как мала насколько это возможно.
Существует ли алгоритм для поиска или приближенного решения подобных проблем?
Я создал возможное решение и реализацию на C#. Надеюсь, это то, что вам нужно. Было бы неплохо, если бы кто-то доказал, что это правильно/неправильно, но это работает, и результаты выглядят правильно. Подробности теории ниже. Его сложность примерно равна O(N!*M^3*Log2(N)), где N — количество переменных, а M — количество слагаемых всех сумм.
Кстати, для вашего примера это дает такой результат:
c=3, a=2, d=2, b=1
{a+b=3; b+c=4; c+d=5; a+a+d=6; b=1}
max=6
ОБНОВЛЕНИЕ
Теория алгоритма.
Предположим, что переменные упорядочены, например. a >= b >= c >= .... Допустим, набор сумм является мешком, если все суммы в нем различны. Все суммы в Сумке можно разделить на две группы: суммы, не содержащие переменную a, и суммы, содержащие переменную a. Назовем первую группу Head, а вторую — Tail. Обратите внимание, что оба являются сумками, потому что они содержат разные суммы. Мы можем вычесть a из каждой суммы в Хвосте так, чтобы все суммы остались различными (т.е. Хвост по-прежнему Мешок). Таким образом мы получаем две сумки без переменной a.
Аналогично исключаем переменную b из двух Сумок и получаем четыре Сумки. Эту операцию мы повторяем для каждой переменной, пока не получим суммы с последней переменной (допустим, это d). Наименьшее значение d равно 1.
После этого мы можем вернуться к предыдущему шагу и включить переменную c в суммы по решкам. Помните, что у нас много пар Голова-Хвост и нужно соединить их обратно. Для этого мы добавляем c к каждой сумме в каждом хвосте, чтобы суммы из хвоста были отличны от голов.
Как рассчитать c? Идея состоит в том, чтобы вычислить его недействительные значения, а затем взять наименьшее значение, которое не является недействительным и равно или превышает d. Вычисление недопустимых значений тривиально, используя условие HeadSum != TailSum + c => c != HeadSum - TailSum. Для каждой комбинации конечной суммы и верхней суммы мы получаем все недопустимые значения.
Сворачивая все пары Head-Tail обратно и вычисляя каждую переменную, мы получаем решение для случая a >= b >= c >= d. Затем мы вычисляем решение для каждой перестановки a >= b >= c >= d и находим наименьшее из них.
PS Было бы здорово, если бы кто-нибудь предоставил лучшее решение, потому что я думаю, что мой алгоритм является чем-то приближенным (но хорошим приближением) или даже лучше, чтобы доказать это. Хуже всего N! сложность из-за перестановок и я до сих пор понятия не имею, как от этого избавиться.
O(N^2)или лучше. Возможно, вы захотите угадать, какой будет самая высокая сумма, а затем попытаться увидеть, возможно ли это. Чем выше угаданная сумма по сравнению с фактической суммой, тем легче должно быть найти допустимое (если не оптимальное) решение. - person Nuclearman schedule 03.12.2014