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

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

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

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

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

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

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

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

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

В двумерном массиве найти минимальный элемент - C++
В двумерном массиве найдите минимальный элемент и поменяйте его местами с элементом A

Найти 5 наибольших элементов в двумерном массиве - C++
В двумерном массиве нужно найти 5 наибольших элементов и вывести их на экран с указанием их индексов. Я только начал изучать C++, код...

Найти максимум и минимум в двумерном массиве - C++
где ошибка Спрашивает, как заполнить двум массив, ищет max и min #include <iostream> #include <ctime> using namespace...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3690 / 1965 / 514
Регистрация: 18.10.2014
Сообщений: 3,544
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Эксперт С++
3690 / 1965 / 514
Регистрация: 18.10.2014
Сообщений: 3,544
02.04.2016, 11:37     Найти максимальную выборку в двумерном массиве #4
Цитата Сообщение от Nikort7 Посмотреть сообщение
Нет, отрицательных чисел нет. Только положительные. И тут надо расставить так "фигуры", чтобы получился максимальный доход, как для равных н и м, так и для разных.
Если матрица квадратна, то вы получаете Задачу о Назначениях (https://ru.m.wikipedia.org/wiki/Задача_о_назначениях), с той только разницей, что классическая формулировка задачи о назначениях старается минимизировать, а не максимизировать сумму. Понятно, что можно "перевернуть" ваши исходные значения и искать минимальную сумму. Задача о Назначениях решается Венгерским алгоритмом: https://ru.m.wikipedia.org/wiki/Венгерский_алгоритм

Если ваша исходная матрица неквадратна, то ее можно просто дополнить нулями до квадратной (думаю, нет ли тут каких подводных камней).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.04.2016, 13:31     Найти максимальную выборку в двумерном массиве
Еще ссылки по теме:

Найти в двумерном массиве максимальный элемент - C++
Нужно создать двумерный массив одним из способов: - вручную -автозаполнением (case) И затем найти максимаьный елемент вот с...

В двумерном массиве найти совершенные числа - C++
Написать программу в с++ которая задает двумерный массив(который нужно вводить с клавиатуры) и ищет в нем совершенное число, выводя его на...

Найти количество нулей в двумерном массиве - C++
Написать программу, которая случайным образом заполняет двумерный массив размерностью 3х4 цифрами от 0 до 10. Необходимо найти...

В двумерном массиве найти последний четный элемент - C++
Дан массив размером n×n, элементы которого целые числа. Для каждой строки найти последний четный элемент и записать данные в новый массив.

Найти сумму в главной диагонали в двумерном массиве - C++
Найти сумму в главной диагонали в двумерном массиве. Пожалуйста, помогите мне)

Найти количество квадратов из единиц в двумерном массиве - C++
Добрый день. Я начинающий программист. Решаю задачки и вот столкнулся с такой пробл.: Почему при вводе данных: 1 - кол-во...


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

Или воспользуйтесь поиском по форуму:
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