Столкнулся с задачкой, которую легко переформулировать в терминах олимпиадного программирования. Уверен, такое решалось 100000 раз, но я что-то не придумал быстро элегантного решения (теряются навыки ACM) :)
n друзей посидели в кафе и расплатились не оставив ни копейки чаевых. Кто-то заплатил больше, чем он должен, кто-то меньше. Теперь друзьям надо рассчитаться друг с другом, при этом передавая деньги из рук в руки наименьшее число раз.
Формально так: есть n целых чисел (балансы друзей), сумма этих чисел равна 0. За ход можно взять пару чисел и прибавить произвольное целое число к первому числу этой пары, при этом отняв от второго.
n1, n2 -> n1'=n1+k, n2'=n2-k
Задача — за наименьшее число ходов превратить все числа в 0.
Не смог убедить себя, что жадный алгоритм работает :)
Единственное, что придумал — пролить макспоток минимальной стоимости через граф с истоком, стоком, слоем должников и слоем кредиторов, где каждый должник соединен с каждым кредитором ребром с пропускной способностью бесконечность. При этом функция стоимости будет странная — 1 если по ребру течет какой-то поток и 0 в противном случае. Вообще не уверен, что алгоритм нахождения потока будет работать с такой функцией.
Короче говоря, я уверен, что это какая-то стандартная задача. Кто напомнит как такое решать?
Кстати, задача становится немного интереснее, если добавить ограничение на номинал купюр, которые есть у друзей.
Пусть есть много(n) положительных чисел и два отрицательных вида -SUM/2
Тогда проверить возможность оплаты в n транзакций — вариация задачи о рюкзаке(набрать sum/2 как подмножество).
То есть при отсутствии ограничений на числа за полином от кол-ва решения не будет.
Промахнулся с ответом, сорри
Да, вроде верно. Я прозрел :)
Ок, как в таком случае решать это вообще, пусть даже за экспоненту? Если числа не очень большие (скажем до 1000) и n не больше 30. Нужна какая-то динамика с масками тогда.
В общем, в таком случае задача такая — придумать алгоритм решения, который будет работать для максимального n и величины чисел. Может MITM какой-нибудь запихнуть можно?
Что нам мешает обнулять все числа в порядке уменьшения их баланса? Пусть A-минимальный баланс, B-максимальный, тогда делаем присваивание A - = K и B + = K, где K = min(A, - B). Если если число A или B становится 0, то просто говорим говорим, что дальше мы его рассматривать не будем, т.к. для него задача уже решена.
Поправьте меня, если я не прав.
Это не оптимально?
Пусть есть числа 3 3 2 2 2 -6 -6. Все укладывается в 5 операций, у вас тройки пойдут в разные 6-ки и дальше уже 3х операций не хватит
Да, действительно. А если это же максимальное на данный момент число A ложить в самое большое число B, что B + A < = 0. Тогда вроде на каждом шаге мы обнуляем как минимум один элемент. Или это тоже неверно?)
upd. Если такого числа B не нашлось, то множим все числа на -1 и пробуем еще раз.
upd. Понял, что тоже неверно, но контр-пример так и не придумал.
Возьмем числа (10, 9) и (-8, -5, -5, -1)
По вашему алгоритму получится такое решение:
1) (2, 9) — (0, -5, -5, -1)
2) (2, 4) — (0, 0, -5, -1)
3) (2, 0) — (0, 0, -1, -1)
4) (1, 0) — (0, 0, 0, -1)
5) (0, 0) — (0, 0, 0, 0)
Хотя можно оптимальнее:
1) (5, 9) — (-8, 0, -5, -1)
2) (0, 9) — (-8, 0, 0, -1)
3) (0, 1) — (0, 0, 0, -1)
4) (0, 0) — (0, 0, 0, 0)
Опять протормозил, что-то сервер CF тупит сегодня
Тут скорее не экспоненциальное надо, а неточное искать. Понятно, что жадно можно решить на n - 1, где n — количество ненулевых чисел (вливать все время наименьший по модулю). И ясно, что меньше, чем за max(#positive, #negative) нельзя. Поэтому имеет смысл применять какую-то такую эвристику — вначале искать все пары x, - x и исключать их, потом перебирать тройки с x + y + z = 0 исключать их и тд, а в конце жадно добивать оставшееся.
Можно еще попробовать какой-нибудь генетический алгоритм, я знаю они хорошо работают в рюкзаках :) Тут правда сложно оптимизировать, т.к. если минимизировать только число транзакций, то непонятно в какую сторону двигаться чтобы уменьшить их число.