Форум программистов, компьютерный форум CyberForum.ru

Найти максимальную выборку в двумерном массиве - C++

Восстановить пароль Регистрация
 
Nikort7
0 / 0 / 0
Регистрация: 12.12.2015
Сообщений: 8
01.04.2016, 23:10     Найти максимальную выборку в двумерном массиве #1
Здравствуйте. Есть массив n на m. Как в нем найти максимальную выборку так, чтобы элементы не стояли на одной строке или одном столбце (по сути - задача как о 8ми ферзях, но только у каждого поля доски есть ценность).
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2908 / 1444 / 397
Регистрация: 18.10.2014
Сообщений: 2,662
01.04.2016, 23:50     Найти максимальную выборку в двумерном массиве #2
Цитата Сообщение от Nikort7 Посмотреть сообщение
Как в нем найти максимальную выборку
Принципиальным моментом тут является то, может ли матрица содержать отрицательные значения и нули.

Если все элементы матрицы положительны, то максимальная выборка всегда будет иметь строго min(m, n) элементов, т.е. будет покрывать все строки и/или столбцы. Но если есть отрицательные элементы, то максимальная выборка может содержать меньше элементов (в т.ч. быть пустой).

Так что там у нас в матрице?
Nikort7
0 / 0 / 0
Регистрация: 12.12.2015
Сообщений: 8
02.04.2016, 10:51  [ТС]     Найти максимальную выборку в двумерном массиве #3
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Принципиальным моментом тут является то, может ли матрица содержать отрицательные значения и нули.

Если все элементы матрицы положительны, то максимальная выборка всегда будет иметь строго min(m, n) элементов, т.е. будет покрывать все строки и/или столбцы. Но если есть отрицательные элементы, то максимальная выборка может содержать меньше элементов (в т.ч. быть пустой).

Так что там у нас в матрице?
Нет, отрицательных чисел нет. Только положительные. И тут надо расставить так "фигуры", чтобы получился максимальный доход, как для равных н и м, так и для разных.
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2908 / 1444 / 397
Регистрация: 18.10.2014
Сообщений: 2,662
02.04.2016, 11:37     Найти максимальную выборку в двумерном массиве #4
Цитата Сообщение от Nikort7 Посмотреть сообщение
Нет, отрицательных чисел нет. Только положительные. И тут надо расставить так "фигуры", чтобы получился максимальный доход, как для равных н и м, так и для разных.
Если матрица квадратна, то вы получаете Задачу о Назначениях (https://ru.m.wikipedia.org/wiki/Задача_о_назначениях), с той только разницей, что классическая формулировка задачи о назначениях старается минимизировать, а не максимизировать сумму. Понятно, что можно "перевернуть" ваши исходные значения и искать минимальную сумму. Задача о Назначениях решается Венгерским алгоритмом: https://ru.m.wikipedia.org/wiki/Венгерский_алгоритм

Если ваша исходная матрица неквадратна, то ее можно просто дополнить нулями до квадратной (думаю, нет ли тут каких подводных камней).
Nikort7
0 / 0 / 0
Регистрация: 12.12.2015
Сообщений: 8
02.04.2016, 13:31  [ТС]     Найти максимальную выборку в двумерном массиве #5
Я просматривал венгерский метод, но необходимо сделать через алгоритм с возвратом (бек-трекинг).
Yandex
Объявления
02.04.2016, 13:31     Найти максимальную выборку в двумерном массиве
Ответ Создать тему
Опции темы

Текущее время: 18:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru