1

Имеется массив целых положительных чисел размерами n на m. Можно брать только один элемент из каждой строки и столбца. Необходимо найти максимально возможную сумму элементов и отобразить их.

образец массива:

350 250 250 100 100 100 100 100 42  21  42  84  0   0   0
250 250 250 100 100 100 100 100 0   0   0   0   63  0   0
350 250 250 100 100 100 100 100 0   21  42  84  21  15  15
150 190 250 0   0   0   0   0   0   0   0   0   0   0   0
350 250 250 100 100 0   100 100 42  42  42  63  63  15  15
300 250 250 100 100 100 100 100 21  21  0   63  84  0   0
250 250 190 100 100 100 100 100 0   21  21  0   0   0   0
300 220 250 0   0   0   100 0   0   0   0   0   0   0   0
350 250 250 0   0   0   100 0   21  0   0   21  21  0   15

максимальный размер n - 25, m - 35

язык желательно php, но подойдет и псевдокод

1
  • И в чём проблема? поиск в ширину, например, подойдёт.
    – Akina
    13 апр 2018 в 12:11

1 ответ 1

1

Задача сводится к задаче о назначениях и решается Венгерским алгоритмом

Дополним матрицу до квадратной 10-ю строками нулей. Это не изменит значение максимальной суммы. Затем решаем задачу о назначениях для квадратной матрицы (Венгерский алгоритм).

3
  • 1
    ссылки на описание алгоритмов и т.п. это скорее комментарий чем ответ.
    – teran
    13 апр 2018 в 12:37
  • 2
    @teran А каким может быть ответ на такой вопрос, если есть известный алгоритм? Детально расписать алгоритм и привести полную реализацию?
    – MBo
    13 апр 2018 в 13:45
  • 2
    @MBo а почему бы и нет? SO позиционируется как база знаний,а не база ссылок на википедию и гугл. Конечно, мб полный код писать уж слишком, но хотя бы вкратце изложить алгоритм и т.п. По факту ведь тут действительно только ссылка на сторонний источник, как по мне, на качественный ответ это не тянет.
    – teran
    13 апр 2018 в 14:01

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.