Минимизация фактов выплат/перевозок? Доброе время суток!
Сразу к делу.Задача: Некоторая группа людей в количестве N человек, где каждый в разное время занимал у кого-то из этой же группы некоторую сумму денег. Необходимо выяснить каким минимальным количеством фактов выплат можно обойтись, чтобы раздать все долги. На входе подаются транзакции задолжностей. Например:
Вход:
7
D A 2
A D 10
A E 7
A F 6
B F 1
B G 5
C G 2
Выход:
5
A E 7
A F 7
A G 7
B D 2
C D 6
На данный момент я делаю следующее.
1) Ввожу понятие баланса. Изначально у всех баланс нулевой. При считывании очередной транзакции баланс того, кто должен уменьшается, баланс того, кому должны — увеличивается (оба на сумму задолжности).
2) После чтения всех транзакций всех людей можно разделить на две группы: с положительным и отрицательным балансами. С нулевым балансом можно просто отбросить. С отрицательным балансом — те, кто должен (поставщики), с положительным — те, кому должны (потребители). Сумма всех значений всегда равна нулю (т.к. количество отданных денег равна количеству полученных). После разделения все значения делаю положительными.
3) Строится транспортная сеть: добавляется исток и соединяется ребрами с каждым поставщиком, максимальная пропускная способность каждого ребра равна значению отдачи, тоже самое делается с потребителями: от них строятся ребра к добавленному стоку. Максимальная пропускная способность каждого такого ребра: значение получения. Между каждой парой поставщика и потребителя строится ребро с бесконечной пропускной способоностью (или с общей суммой отдачи/получения).
4) запускается алгоритм Форда-Фалкерсона — получаем некоторый базис. Он в общем случае еще не оптимален.
На данном этапе я застрял. Дальше не знаю что делать (все варианты которые я перепробовал — не работают, если необходимо — могу расписать что делал).
Вопрос: как минизировать количество выплат? Спасибо!
P.S. Не стал писать математическую формализацию задачи в виде системы линейных уравнений и функции, которую надо минимизировать. Если надо — сообщите об этом в комментариях.
Минимизация фактов выплат/перевозок? Доброе время суток!
Сразу к делу.Задача: Некоторая группа людей в количестве N человек, где каждый в разное время занимал у кого-то из этой же группы некоторую сумму денег. Необходимо выяснить каким минимальным количеством фактов выплат можно обойтись, чтобы раздать все долги. На входе подаются транзакции задолжностей. Например:
Вход:
7
D A 2
A D 10
A E 7
A F 6
B F 1
B G 5
C G 2
Выход:
5
A E 7
A F 7
A G 7
B D 2
C D 6
На данный момент я делаю следующее.
1) Ввожу понятие баланса. Изначально у всех баланс нулевой. При считывании очередной транзакции баланс того, кто должен уменьшается, баланс того, кому должны — увеличивается (оба на сумму задолжности).
2) После чтения всех транзакций всех людей можно разделить на две группы: с положительным и отрицательным балансами. С нулевым балансом можно просто отбросить. С отрицательным балансом — те, кто должен (поставщики), с положительным — те, кому должны (потребители). Сумма всех значений всегда равна нулю (т.к. количество отданных денег равна количеству полученных). После разделения все значения делаю положительными.
3) Строится транспортная сеть: добавляется исток и соединяется ребрами с каждым поставщиком, максимальная пропускная способность каждого ребра равна значению отдачи, тоже самое делается с потребителями: от них строятся ребра к добавленному стоку. Максимальная пропускная способность каждого такого ребра: значение получения. Между каждой парой поставщика и потребителя строится ребро с бесконечной пропускной способоностью (или с общей суммой отдачи/получения).
4) запускается алгоритм Форда-Фалкерсона — получаем некоторый базис. Он в общем случае еще не оптимален.
На данном этапе я застрял. Дальше не знаю что делать (все варианты которые я перепробовал — не работают, если необходимо — могу расписать что делал).
Вопрос: как минизировать количество выплат? Спасибо!
P.S. Не стал писать математическую формализацию задачи в виде системы линейных уравнений и функции, которую надо минимизировать. Если надо — сообщите об этом в комментариях.
Сразу к делу.Задача: Некоторая группа людей в количестве N человек, где каждый в разное время занимал у кого-то из этой же группы некоторую сумму денег. Необходимо выяснить каким минимальным количеством фактов выплат можно обойтись, чтобы раздать все долги. На входе подаются транзакции задолжностей. Например:
Вход:
7
D A 2
A D 10
A E 7
A F 6
B F 1
B G 5
C G 2
Выход:
5
A E 7
A F 7
A G 7
B D 2
C D 6
На данный момент я делаю следующее.
1) Ввожу понятие баланса. Изначально у всех баланс нулевой. При считывании очередной транзакции баланс того, кто должен уменьшается, баланс того, кому должны — увеличивается (оба на сумму задолжности).
2) После чтения всех транзакций всех людей можно разделить на две группы: с положительным и отрицательным балансами. С нулевым балансом можно просто отбросить. С отрицательным балансом — те, кто должен (поставщики), с положительным — те, кому должны (потребители). Сумма всех значений всегда равна нулю (т.к. количество отданных денег равна количеству полученных). После разделения все значения делаю положительными.
3) Строится транспортная сеть: добавляется исток и соединяется ребрами с каждым поставщиком, максимальная пропускная способность каждого ребра равна значению отдачи, тоже самое делается с потребителями: от них строятся ребра к добавленному стоку. Максимальная пропускная способность каждого такого ребра: значение получения. Между каждой парой поставщика и потребителя строится ребро с бесконечной пропускной способоностью (или с общей суммой отдачи/получения).
4) запускается алгоритм Форда-Фалкерсона — получаем некоторый базис. Он в общем случае еще не оптимален.
На данном этапе я застрял. Дальше не знаю что делать (все варианты которые я перепробовал — не работают, если необходимо — могу расписать что делал).
Вопрос: как минизировать количество выплат? Спасибо!
P.S. Не стал писать математическую формализацию задачи в виде системы линейных уравнений и функции, которую надо минимизировать. Если надо — сообщите об этом в комментариях.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для минимизации количества выплат в данной задаче можно воспользоваться алгоритмом поиска максимального потока в сети, таким как алгоритм проталкивания предпотока или алгоритм Эдмондса-Карпа.
Сначала построим сеть следующим образом:
Создадим исток и сток.Для каждого поставщика соединим исток ребром с пропускной способностью, равной абсолютному значению его отрицательного баланса.Для каждого потребителя соединим сток ребром с пропускной способностью, равной абсолютному значению его положительного баланса.Добавим ребра между каждой парой поставщика и потребителя с бесконечной пропускной способностью.Затем запустим алгоритм поиска максимального потока в этой сети. Получившийся поток будет представлять собой оптимальное распределение долгов, минимизируя количество выплат.
Дополнительно, можно использовать алгоритм Хопкрофта-Карпа для поиска наилучшего паросочетания в графе, что также позволит минимизировать количество выплат.