|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 20 Nov 2001 19:08:00
To : Aleksey Nilov
Subject : Задача по комбинаторике...
--------------------------------------------------------------------------------
Replying to a message of Aleksey Nilov to Max Alekseyev:
AN>>> Вот тут задали задачу. Hе знаю как сделать. Может быть
AN>>> многоуважаемый алл поможет? Собсно задача: Дана матрица C[N,N].
AN>>> 1..N - условно обозначены предприятия. Матрица составлена
AN>>> следующим образом: С[i,j] элемент - сколько предприятие i должно
AN>>> предприятию j (денег). Преобразовать матрицу так, что-бы число
AN>>> операций по передаче денег было минимальным.
MA>>
MA>> Сначала упростим задачу: положим B[i] = сумма по всем j чисел C[i,j]
MA>> Числа B[i] соответствуют долгам или кредитам предприятий, причем
MA>> неважно кто кому должен, важно что сумма всех B[i] равна 0. Теперь
MA>> задача состоит в разбиении множества { B[1], B[2], ..., B[N] } на
MA>> как можно большее число непересекающихся подмножеств, сумма
MA>> элементов которых равна 0. Действительно, нетрудно показать, что
MA>> если такое подмножество состоит из t элементов, то взаимозачет в
MA>> нем можно осуществить не более чем за t-1 транзакций. Можно также
MA>> показать, что если это такое подмножество минимально (т.е. не
MA>> содержит собственного непустого подмножества с нулевой суммой), то
MA>> для взаимозачета требуется не менее t-1 транзакций. Итак, если
MA>> удастся исходное множество { B[1], B[2], ..., B[N] } разбить на k
MA>> подмножеств с нулевой суммой, то для взаимозачета потребуется N-k
MA>> транзакций. Задача состоит в максимизации k.
AN> Понятно, спасибо...
AN> Hо помимо числа транзакций нам необходимо получить некоторую матрицу
AN> D[N,N], которой будут описаны те самые N-k транзакций (таким же
AN> образом как и в исходной C[N,N])... как ее получить?
Если { A[1], ..., A[t] } множество с нулевой суммой, то "раздать долги" можно
следующим образом
D[1,2] = - A[1]
D[2,3] = - A[2] - A[1]
D[3,4] = - A[3] - A[2] - A[1]
...
D[t-1,t] = - A[t-1] - ... - A[1] = A[t]
Всего t-1 транзакций.
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.7
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
