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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Nikort7
0 / 0 / 0
Регистрация: 12.12.2015
Сообщений: 12
#1

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

01.04.2016, 23:10. Просмотров 172. Ответов 4
Метки нет (Все метки)

Здравствуйте. Есть массив n на m. Как в нем найти максимальную выборку так, чтобы элементы не стояли на одной строке или одном столбце (по сути - задача как о 8ми ферзях, но только у каждого поля доски есть ценность).
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.04.2016, 23:10     Найти максимальную выборку в двумерном массиве
Посмотрите здесь:

C++ Найти в двумерном массиве максимальный элемент
C++ Найти сумму в главной диагонали в двумерном массиве
C++ Найти максимальную сумму значений элементов строки в массиве
C++ Найти количество нулей в двумерном массиве
C++ В двумерном массиве найти последний четный элемент
Найти максимум и минимум в двумерном массиве C++
C++ Найти сумму одинаковых чисел в двумерном массиве
C++ Найти в массиве чисел последовательность, имеющую максимальную сумму
В двумерном массиве найти минимальный элемент C++
В двумерном массиве найти совершенные числа C++
C++ Найти количество квадратов из единиц в двумерном массиве
Найти 5 наибольших элементов в двумерном массиве C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3614 / 1889 / 501
Регистрация: 18.10.2014
Сообщений: 3,451
01.04.2016, 23:50     Найти максимальную выборку в двумерном массиве #2
Цитата Сообщение от Nikort7 Посмотреть сообщение
Как в нем найти максимальную выборку
Принципиальным моментом тут является то, может ли матрица содержать отрицательные значения и нули.

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

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

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

Так что там у нас в матрице?
Нет, отрицательных чисел нет. Только положительные. И тут надо расставить так "фигуры", чтобы получился максимальный доход, как для равных н и м, так и для разных.
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3614 / 1889 / 501
Регистрация: 18.10.2014
Сообщений: 3,451
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
Сообщений: 12
02.04.2016, 13:31  [ТС]     Найти максимальную выборку в двумерном массиве #5
Я просматривал венгерский метод, но необходимо сделать через алгоритм с возвратом (бек-трекинг).
Yandex
Объявления
02.04.2016, 13:31     Найти максимальную выборку в двумерном массиве
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru