|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Aleksey Nilov 2:5038/14.18 21 Nov 2001 02:42:20
To : Max Alekseyev
Subject : RE:Задача по комбинаторике...
--------------------------------------------------------------------------------
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>
MA> Теперь задача состоит в разбиении множества { B[1], B[2], ..., B[N] } на
MA> как можно большее число непересекающихся подмножеств, сумма элементов
MA> которых равна 0.
MA>
MA> Действительно, нетрудно показать, что если такое подмножество состоит из
MA> t элементов, то взаимозачет в нем можно осуществить не более чем за t-1
MA> транзакций. Можно также показать, что если это такое подмножество
MA> минимально (т.е. не содержит собственного непустого подмножества с
MA> нулевой суммой), то для взаимозачета требуется не менее t-1 транзакций.
MA>
MA> Итак, если удастся исходное множество { B[1], B[2], ..., B[N] } разбить
MA> на k подмножеств с нулевой суммой, то для взаимозачета потребуется N-k
MA> транзакций. Задача состоит в максимизации k.
Понятно, спасибо...
Hо помимо числа тpанзакций нам необходимо получить некотоpую матpицу D[N,N],
котоpой будут описаны те самые N-k тpанзакций (таким же обpазом как и в исходной
C[N,N])... как ее получить?
С уважением, Алексей илов
--- FIPS/32 v0.99b W95/NT [Unreg]
* Origin: (2:5038/14.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
RE:Задача по комбинаторике... 