Каков наилучший способ найти максимально возможную сумму в массиве 2D целого числа? Вы не можете повторять столбцы и строки. Например.Наивысшая возможная сумма по двумерному массиву
1 3 6
4 5 2
3 1 3
Max sum: 3+5+6=14
Я знаю, что существует метод, называемый венгерским алгоритмом, но это, по-видимому, более подходит для поиска минимальной суммы.
Да, вы можете использовать венгерский алгоритм.
Вам необходимо изменить критерии поиска, чтобы найти самую большую сумму вместо самых маленьких. Вам также нужно запустить Bellman-Ford вместо Dijkstra для компонента поиска (потому что Dijkstra не может вычислить максимальный путь суммы).
Вы не можете столкнуться с постоянно увеличивающимся циклом, потому что выбранные узлы уже спарены с использованием их максимального значения, поэтому любое изменение даст более низкую общую сумму. Алгоритм будет выбирать переупорядочивать соединения, если потери от уже подключенных узлов меньше коэффициента усиления от недавно подключенного. Вам не нужно беспокоиться об этом.
Ваш вопрос непонятен, какие элементы вы включаете в сумму? Должны ли они быть смежными? Выбираете ли вы весь столбец или строку? –
Изменено для уточнения. – user3918985
Лучший способ, о котором я могу думать, - это динамическое программирование. Например: http://stackoverflow.com/questions/11621337/java-maximum-sum-in-path-through-a-2d-array –