2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Поиск максимальной суммы не соседних элементов матрицы
Сообщение12.12.2018, 23:17 


12/12/18
3
Всем привет!
Столкнулась вот с какой задачей. Матрица чисел задана двумерным массивом. Обязательное условие, чтобы в ней было 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));
    }
}

 Профиль  
                  
 
 Posted automatically
Сообщение12.12.2018, 23:29 


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

 Профиль  
                  
 
 Re: Поиск максимальной суммы не соседних элементов матрицы
Сообщение12.12.2018, 23:35 
Заслуженный участник
Аватара пользователя


16/07/14
8338
Цюрих
17clever в сообщении #1360874 писал(а):
Максимально возможная сумма на самом деле 8.
Откуда 8? У меня получается либо 7 (если брать только два элемента), либо 9 (если можно брать больше двух).

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

 Профиль  
                  
 
 Re: Поиск максимальной суммы не соседних элементов матрицы
Сообщение12.12.2018, 23:45 


12/12/18
3
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?

 Профиль  
                  
 
 Re: Поиск максимальной суммы не соседних элементов матрицы
Сообщение12.12.2018, 23:51 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
17clever в сообщении #1360874 писал(а):
Моя идея заключалась в том, чтобы брать первую колонку и смотреть сумма каких её элементов, удовлетворяющих условие, больше – 1 и 3 или 2 и 4. Записав их сумму и индексы пройтись циклом дальше, суммируя элементы с противоположными индексами и перезаписывая номера этих индексов для следующей итерации.
Звучит как-то сложно. Фактически, вам нужно записать ваши числа на "шахматную доску" и посчитать, какая сумма больше - сумма чисел на черных клетках или сумма чисел на белых. Алгоритм дает сбой из-за того, что есть много нулей - их можно проигнорировать вообще, но выбрать числа через ряд с нарушением шахматного порядка.
Я бы попробовал разбить алгоритм на "базовый" - подсчет в шахматном порядке, и добавил "улучшения" - когда можно сбить порядок на небольшом участке и пересчитать его. Но это очень муторно.

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

 Профиль  
                  
 
 Re: Поиск максимальной суммы не соседних элементов матрицы
Сообщение12.12.2018, 23:52 
Заслуженный участник


04/03/09
906
17clever в сообщении #1360884 писал(а):
Как у вас получилось 9?

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

 Профиль  
                  
 
 Re: Поиск максимальной суммы не соседних элементов матрицы
Сообщение12.12.2018, 23:54 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
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. Опередили, как водится...

 Профиль  
                  
 
 Re: Поиск максимальной суммы не соседних элементов матрицы
Сообщение13.12.2018, 01:56 


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

12d3 в сообщении #1360887 писал(а):
1) Знакомы ли вы с понятием динамического программирования.

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

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Поиск максимальной суммы не соседних элементов матрицы
Сообщение13.12.2018, 02:05 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
17clever в сообщении #1360910 писал(а):
Боюсь, что добавление "улучшений" превысит временную сложность $O(n)$, а это еще одно из условий задания, которого желательно придерживаться.
Ничего не путаете со сложностью? Что-то мне подсказывает, что в нее вот совсем никак не уложиться.

 Профиль  
                  
 
 Re: Поиск максимальной суммы не соседних элементов матрицы
Сообщение13.12.2018, 02:24 
Заслуженный участник
Аватара пользователя


16/07/14
8338
Цюрих
Правильный подход тут - именно обобщение одномерного случая (по крайней мере, оно очень простое, а других простых подходов я за 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$.

 Профиль  
                  
 
 Re: Поиск максимальной суммы не соседних элементов матрицы
Сообщение13.12.2018, 11:47 


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

 Профиль  
                  
 
 Re: Поиск максимальной суммы не соседних элементов матрицы
Сообщение15.12.2018, 21:13 


28/07/17

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group