Алгоритм аппроксимации оптимального решения задачи целочисленного размещения

Question

У меня есть следующая проблема:

Для заданного набора сумм переменных, таких как { a + b, b + c, c + d, a + a + d, b }, найдите положительные целочисленные значения для переменных, чтобы все суммы были различны, а максимальная сумма мала насколько это возможно.

Есть ли алгоритм, чтобы найти или приблизить решение такого рода проблем?

Answer 1

Я создал возможное решение и реализацию в 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 и суммы, которые содержат. Давайте назовем первую группу Главой, а вторую - Хвостом. Обратите внимание, что оба пакета являются Bags, поскольку они содержат разные суммы. Мы можем вычесть a от каждой суммы в хвосте, так что все суммы остаются разными (то есть, хвост остается сумкой). Таким образом, мы получаем две сумки без переменных a,

Подобным образом мы исключаем переменную b из двух сумок и получите четыре сумки. Эту операцию мы повторяем для каждой переменной, пока не получим суммы с последней переменной (скажем, это d). Наименьшее значение d это 1.

После этого мы можем вернуться к предыдущему шагу и включить переменную c в суммах от хвостов. Помните, что у нас много пар Head-Tail и мы должны присоединиться к ним. Для этого мы добавляем c к каждой сумме в каждом Хвосте так, чтобы суммы из Хвоста отличались от Головы.

Как рассчитать c? Идея состоит в том, чтобы вычислить его недопустимые значения и затем принять наименьшее значение, которое не является недействительным, а также равно или больше, чем d, Вычисление неверных значений тривиально, используя условие HeadSum != TailSum + c => c != HeadSum - TailSum, Для каждой комбинации суммы хвоста и суммы головы мы получаем все недопустимые значения.

Свернув все пары Head-Tail и вычислив каждую переменную, мы получим решение для случая a >= b >= c >= d, Затем мы вычисляем решение для каждой перестановки a >= b >= c >= d и найти самый маленький.

PS Было бы замечательно, если бы кто-то предложил лучшее решение, потому что я думаю, что мой алгоритм в некоторой степени приближенный (но хороший пример) или даже лучше доказать это. Самое страшное N! сложность из-за перестановок, и я до сих пор не знаю, как от нее избавиться.