0 / 0 / 0
Регистрация: 12.12.2015
Сообщений: 21
1

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

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

Author24 — интернет-сервис помощи студентам
Здравствуйте. Есть массив n на m. Как в нем найти максимальную выборку так, чтобы элементы не стояли на одной строке или одном столбце (по сути - задача как о 8ми ферзях, но только у каждого поля доски есть ценность).
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.04.2016, 23:10
Ответы с готовыми решениями:

Найти максимальную возрастающую подпоследовательность в одномерном массиве
Помогите найти максимальную возрастающую подпоследовательность в одномерном массиве.

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

Найти максимум в двумерном массиве
Доброго времени суток. Опять-таки переписываю с дельфи на ассемблер. Задача проста - найти максимум...

в двумерном массиве найти путь
Задан двумерный массив A. требуется найти такой путь из A в d, проходящий через соседние...

4
Вездепух
Эксперт CЭксперт С++
11691 / 6370 / 1723
Регистрация: 18.10.2014
Сообщений: 16,052
01.04.2016, 23:50 2
Цитата Сообщение от Nikort7 Посмотреть сообщение
Как в нем найти максимальную выборку
Принципиальным моментом тут является то, может ли матрица содержать отрицательные значения и нули.

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

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

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

Так что там у нас в матрице?
Нет, отрицательных чисел нет. Только положительные. И тут надо расставить так "фигуры", чтобы получился максимальный доход, как для равных н и м, так и для разных.
0
Вездепух
Эксперт CЭксперт С++
11691 / 6370 / 1723
Регистрация: 18.10.2014
Сообщений: 16,052
02.04.2016, 11:37 4
Цитата Сообщение от Nikort7 Посмотреть сообщение
Нет, отрицательных чисел нет. Только положительные. И тут надо расставить так "фигуры", чтобы получился максимальный доход, как для равных н и м, так и для разных.
Если матрица квадратна, то вы получаете Задачу о Назначениях (https://ru.m.wikipedia.org/wik... азначениях), с той только разницей, что классическая формулировка задачи о назначениях старается минимизировать, а не максимизировать сумму. Понятно, что можно "перевернуть" ваши исходные значения и искать минимальную сумму. Задача о Назначениях решается Венгерским алгоритмом: https://ru.m.wikipedia.org/wik... й_алгоритм

Если ваша исходная матрица неквадратна, то ее можно просто дополнить нулями до квадратной (думаю, нет ли тут каких подводных камней).
1
0 / 0 / 0
Регистрация: 12.12.2015
Сообщений: 21
02.04.2016, 13:31  [ТС] 5
Я просматривал венгерский метод, но необходимо сделать через алгоритм с возвратом (бек-трекинг).
0
02.04.2016, 13:31
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.04.2016, 13:31
Помогаю со студенческими работами здесь

Найти максимальную сумму значений элементов строки в массиве
#define _CRT_SECURE_NO_WARNINGS #define _CRT_NONSTDC_NO_WARNINGS #include <stdio.h>...

Найти в массиве чисел последовательность, имеющую максимальную сумму
Написать программу, находящую в массиве вещественных чисел последовательность, имеющую максимальную...

Найти максимальную сумму двух соседних элементов в массиве
помогите пожалуйста решить задачу:в одномерном массиве найти максимальную сумму двух соседних...

Найти максимальную последовательность повторяющихся чисел в одномерном массиве
Вывести одномерный массив (30 элементов в интервале) и определить в нём максимальную...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru