Задача про матрицу

zerocool1900

Дана матрица размера N * kN, заполненная числами от 0 до 1. Необходимо выбрать из нее kN чисел так, чтобы из каждой строки было выбрано ровно одно число, а из каждого столбца ровно k чисел и их сумма была максимальной.
У меня пока кроме тупого перебора нет вариантов :confused:

mtk79

числа от 0 до 1 могут быть:
— кратными 1/m
— рациональными
— действительными
Вы считаете, что это одна и та же задача?

Vlad128

а я вообще сидел и думал на случаем
— целыми :)

griz_a

А я вообще думал над тем, как это у матрицы N строк, а берется kN элементов по одному элементу из каждой строки :)

Vlad128

ну с этим я разобрался :grin:

zerocool1900

Разницы не вижу, но пусть будут рациональные. Причем для того чтобы найти максимальную сумму, можно умножить на общий знаменатель и будут целые.

iri3955

Для k = 1 можно так.
d(n, m) - m элементов матрицы (N-n) x (N-n) (нижнего правого минора) с максимальной суммой, никакие 2 из которых не лежат в одной строке и одном столбце.
Вычитая из матрицы строки и столбцы вида (a, a, a, ..., a) добиваемся, что в n-x строке и столбце нули.
В оставшемся квадрате (N-n-1) x (N-n-1) ищем d(n+1, m) и d(n+1, m-1).
Если d(n+1, m) > d(n+1, m-1 то d(n, m) состоит из d(n+1, m) и элемента (n,n иначе из d(n+1,m-1) и недостающих элементов из n-x строки и столбца.
Надо найти d(0, N сложность порядка N^3. Если элементы не занулять, просто на каждом этапе n считать, что A(i, j) = A(i, j) + A(n, n) - A(n, j) - A(i, n то сложность - N^2.
Вроде не напутал. Возможно, обобщается до N x kN.

a101

http://ru.wikipedia.org/wiki/%D0%92%D0%B5%D0%BD%D0%B3%D0%B5%...
Это для k=1.
Дальше можно продублицировать столбцы или подправить алгоритм.
Но вообще это Min-Cost-Flow. Если ограничить поток на каждый столбец k а на каждую строку 1, то финально будет построено решение то, которое требуется (хоть это и не очевидно).
http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%82%D0%BE%D0%BA_...
Оставить комментарий
Имя или ник:
Комментарий: