Поиск максимальной суммы не соседних элементов матрицы

[17clever]

Всем привет!
Столкнулась вот с какой задачей. Матрица чисел задана двумерным массивом. Обязательное условие, чтобы в ней было 4 ряда (то есть, её размер $4 \times n$). Cтоит задача написать программу, которая бы находила максимальную сумму таких элементов, которые не являются соседями (Если представлять матрицу в виде таблицы, то у этих элементов\ячеек не должно быть общих граней\сторон, но могут быть общие углы).
Моя идея заключалась в том, чтобы брать первую колонку и смотреть сумма каких её элементов, удовлетворяющих условие, больше – 1 и 3 или 2 и 4. Записав их сумму и индексы пройтись циклом дальше, суммируя элементы с противоположными индексами и перезаписывая номера этих индексов для следующей итерации. Такой подход безотказно выполняет условие «суммировать не соседние» элементы, но работает неправильно, например, на таких входных данных:

$\begin{bmatrix} 1 & 2 &5 \\ 2 & 0 & 0 \\ 2 & 0 & 0 \\ 2 & 0 & 0 \\ \end{bmatrix}$

Результат, который выдает программа 6. Максимально возможная сумма на самом деле 8.
Может быть вы подскажете как можно усовершенствовать имеющийся код? Или, если мой подход в корне не верный, подадите идею как по-другому решить это задание?

Используется синтаксис Java

 class GFG {
    public static int maxSum(int grid[][], int n)
    {
        int index1, index2, sum;
        if ((grid[0][0]+grid[2][0])>(grid[1][0]+grid[3][0])) {
            index1 = 0;
            index2 = 2;
            sum = grid[0][0]+grid[2][0];
        } else {
            index1 = 1;
            index2 = 3;
            sum = grid[1][0]+grid[3][0];
        }

        if (n>1) {
        for (int i = 1; i < n; i++ )
        {
            if (index1 == 1 && index2 == 3) {
                index1 = 0;
                index2 = 2;
                sum = sum + grid[0][i]+grid[2][i];
            } else {
                index1 = 1;
                index2 = 3;
                sum = sum + grid[1][i]+grid[3][i];
            }
        }
        }
        return sum;
    }

    public static void main(String[] args)
    {
        int grid[][] = {{ 1, 2, 5},
                        { 2, 0, 0},
                        { 2, 0, 0},
                        { 2, 0, 0}};
        int n = 3;
        System.out.println(maxSum(grid, n));
    }
}

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Программирование»
Причина переноса: не указана.

[mihaild]

17clever в сообщении #1360874 писал(а):

Максимально возможная сумма на самом деле 8.

Откуда 8? У меня получается либо 7 (если брать только два элемента), либо 9 (если можно брать больше двух).

Кроме того, посчитайте на бумажке, какой результат дает ваш метод на этой матрице - если он совпадает с полученным программой, то в методе точно есть ошибка; если отличается - то в программе точно есть ошибка (и в методе, возможно, тоже).

[17clever]

mihaild, Простите, я, наверное, плохо изъяснилась.

Программа работает неправильно (так как в корне лежит мой неправильный алгоритм).
В заданной матрице она суммирует элементы, которые выделены красным. Их сумма 6.

$\begin{bmatrix} 1 & \color{red}2 &5 \\ \color{red}2 & 0 & \color{red}0 \\ 2 & \color{red}0 & 0 \\ \color{red}2 & 0 & \color{red}0 \\ \end{bmatrix}$

Я же хочу добиться того, чтобы программа не просто двигалась по клеточкам, а действительно находила максимальную сумму. В этом случае нужно было суммировать эти элементы:
$\begin{bmatrix} \color{red}1 & 2 &\color{red}5 \\ 2 & \color{red}0 & 0 \\ \color{red}2 & 0 & \color{red}0 \\ 2 & \color{red}0 & 0 \\ \end{bmatrix}$

Как у вас получилось 9?

[rockclimber]

17clever в сообщении #1360874 писал(а):

Моя идея заключалась в том, чтобы брать первую колонку и смотреть сумма каких её элементов, удовлетворяющих условие, больше – 1 и 3 или 2 и 4. Записав их сумму и индексы пройтись циклом дальше, суммируя элементы с противоположными индексами и перезаписывая номера этих индексов для следующей итерации.

Звучит как-то сложно. Фактически, вам нужно записать ваши числа на "шахматную доску" и посчитать, какая сумма больше - сумма чисел на черных клетках или сумма чисел на белых. Алгоритм дает сбой из-за того, что есть много нулей - их можно проигнорировать вообще, но выбрать числа через ряд с нарушением шахматного порядка.
Я бы попробовал разбить алгоритм на "базовый" - подсчет в шахматном порядке, и добавил "улучшения" - когда можно сбить порядок на небольшом участке и пересчитать его. Но это очень муторно.

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

[12d3]

17clever в сообщении #1360884 писал(а):

Как у вас получилось 9?

Две двойки из первой колонки и пятерка из последней. Это полностью соответствует условию задачи в стартовом посте. Либо с условием что-то не так, либо вы его неправильно поняли.
Если все-таки условие приведено верно, то два вопроса.
1) Знакомы ли вы с понятием динамического программирования.
2) Попробуйте решить упрощенный вариант задачки, где всего один ряд вместо четырех. Какие идеи будут?

[rockclimber]

17clever в сообщении #1360884 писал(а):

$\begin{bmatrix} \color{red}1 & 2 &\color{red}5 \\ 2 & \color{red}0 & 0 \\ \color{red}2 & 0 & \color{red}0 \\ 2 & \color{red}0 & 0 \\ \end{bmatrix}$

Как у вас получилось 9?

Элементарно, Ватсон ээээ... 17clever:
$\begin{bmatrix} 1 & 2 &\color{red}5 \\ \color{red}2 & 0 & 0 \\ 2 & 0 & \color{red}0 \\ \color{red}2 & 0 & 0 \\ \end{bmatrix}$

P. S. Опередили, как водится...

[17clever]

rockclimber, 12d3,
Да, вы правы. Метод подсчета по принципу шахматной доски замылил взор и я не подумала, что можно пропускать некоторые колонки.

12d3 в сообщении #1360887 писал(а):

1) Знакомы ли вы с понятием динамического программирования.

Достаточно поверхностно. Знаю лишь то, что это разбиение задачи на мелкие подзадачи их решение.

rockclimber в сообщении #1360888 писал(а):

2) Попробуйте решить упрощенный вариант задачки, где всего один ряд вместо четырех. Какие идеи будут?

Подсмотрела в интернете туториал с готовым алгоритмом и видеобъяснением: https://www.geeksforgeeks.org/maximum-s ... -adjacent/
Если на данном этапе мне стало понятно как разобраться с одномерным массивом, то 2д массив ставит в тупик. Получается, что нужно ввести еще какое-то сравнение c результатом\суммой других строк\колонок на каждом этапе? И как гарантировать, что соблюдается условие о соседстве, точнее его отсутсвии.

rockclimber в сообщении #1360886 писал(а):

Я бы попробовал разбить алгоритм на "базовый" - подсчет в шахматном порядке, и добавил "улучшения" - когда можно сбить порядок на небольшом участке и пересчитать его. Но это очень муторно.

Боюсь, что добавление "улучшений" превысит временную сложность $O(n)$, а это еще одно из условий задания, которого желательно придерживаться.

rockclimber в сообщении #1360886 писал(а):

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

Спасибо, очень интересная идея! Я подумаю как можно это реализовать.

[rockclimber]

17clever в сообщении #1360910 писал(а):

Боюсь, что добавление "улучшений" превысит временную сложность $O(n)$, а это еще одно из условий задания, которого желательно придерживаться.

Ничего не путаете со сложностью? Что-то мне подсказывает, что в нее вот совсем никак не уложиться.

[mihaild]

Правильный подход тут - именно обобщение одномерного случая (по крайней мере, оно очень простое, а других простых подходов я за 10 минут не придумал).
Пусть $f(n)$ - максимальная сумма, получаемая за первые $n$ столбцов. Для одномерного случая $f(n)$ очень просто выражается через $f(n - 1)$ и $f(n - 2)$ - оптимальное решение, включающее $n$-й элемент - это собственно $n$-й элемент и оптимальное решение для первых $n - 2$ элементов. Т.е. когда мы строим из решения для $n-1$ столбца решение для $n$ столбцов нас интересует только брали мы $n-1$-й элемент или нет; какие конкретно предыдущие элементы мы брали - неважно, важна только их сумма.
Переформулируем это: $g(n, 0)$ - это максимальная сумма за первые $n$ столбцов, если $n$-й элемент не брать, а $g(n, 1)$ - максимальная сумма за первые $n$ столбцов, если $n$-й элемент брать. Заметим, что $g(n, x)$ выражается через $g(n - 1, 0)$ и $g(n - 1, 1)$ - попробуйте выписать это выражение явно.
Если строк больше одной, то для перехода от $n - 1$ столбца к $n$ нам уже не хватит простого параметра $0 / 1$. Подумайте, какая информация о решении для первых $n-1$ столбцов нам нужна, чтобы продолжить его до $n$.

[realeugene]

Вопрос: это у вас учебная задача?
Если да - то ограничусь советом посмотреть алгоритм Витерби. Разберётесь в нём - поймёте, как решить вашу задачу за $O(n)$.

[FomaNeverov]

17clever, ну как, решили задачу?