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