Блог

Существует матрица с m строками и n столбцами. Задача состоит в том, чтобы найти максимальную сумму, выбирая один элемент из каждой строки и столбца. Я придумал решение, которое находит максимум из всей матрицы, а затем устанавливает эту строку и столбец равными нулю, добавляет их к сумме и переходит к поиску следующего максимума. Это повторяется m раз.

Но проблема с этим подходом заключалась в наличии повторяющихся элементов. Я попытаюсь объяснить это на примере. Вот матрица..

3 6 5 3

9 4 9 2
8 1 4 3

4 7 2 5

Теперь, если я последую приведенному выше методу .. сумма будет 9 7 5 3 в то время как это должно быть 9 8 7 3 . Как решить эту проблему.. Я застрял

Обновление: столбцы — это стоимость мест, которые могут быть назначены человеку, а строки — количество человек. Мы хотим назначить их таким образом, чтобы получить максимальную стоимость.

Разве это не просто http://en.wikipedia.org/wiki/Assignment_problem , обычно решаемая с помощью http://en.wikipedia.org/wiki/Hungarian_algorithm ? Очевидно, что вам нужен максимум, а не минимум, но, безусловно, вы можете достичь этого, максимизируя затраты, которые составляют — (реальная стоимость) или, если вас беспокоит -пять затрат, (максимальная стоимость в матрице) — (реальная стоимость).

Ваш алгоритм неверен — рассмотрите небольшое изменение в матрице, где вторые 9 равны 8:

 3 6 5 3 
9 4 8 2 
8 1 4 3 
4 7 2 5 
  

Тогда у вашего алгоритма нет проблем с поиском 9, 7, 5, 3 (нет дубликатов), но правильный ответ все еще 8, 8, 7, 3 остается.

Вы можете применить грубую силу, попробовав все комбинации. Один хороший способ поместить это в код — использовать рекурсивную функцию, которая решает проблему для любой матрицы:

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

Это, конечно, будет слишком медленно для больших матриц. Сложность заключается O(N!) в том.