Рубрики

Максимизируйте сумму, выбирая элементы из разных разделов матрицы

Дана матрица из N строк и M столбцов. Задано, что M кратно 3. Столбцы разделены на 3 секции, первая секция от 0 до m / 3-1, вторая секция от m / 3 до 2m / 3-1 и третья секция от 2 м / 3 до м. Задача состоит в том, чтобы выбрать один элемент из каждой строки, и в соседних строках мы не можем выбрать один и тот же раздел. Мы должны максимизировать сумму выбранных элементов.

Примеры:

Input: mat[][] = {
{1, 3, 5, 2, 4, 6},
{6, 4, 5, 1, 3, 2},
{1, 3, 5, 2, 4, 6},
{6, 4, 5, 1, 3, 2},
{6, 4, 5, 1, 3, 2},
{1, 3, 5, 2, 4, 6}}
Output: 35

Input: mat[][] = {
{1, 2, 3},
{3, 2, 1},
{5, 4, 2}
Output: 10

Подход: проблема может быть решена с помощью динамического программирования путем хранения подзадач и их повторного использования. Создайте массив dp [] [], где dp [i] [0] представляет сумму элементов строк от 0 до i, взяв элементы из раздела 1 . Аналогично для dp [i] [1] и dp [i] [2] . Итак, выведите max (dp [n — 1] [0], dp [n — 1] [1], dp [n — 1] [2] .

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа для вышеуказанного подхода
#include <bits/stdc++.h>

using namespace std;

  

const int n = 6, m = 6;

  
// Функция для поиска максимального значения

void maxSum(long arr[n][m])

{

    // таблица дп

    long dp[n + 1][3] = { 0 };

  

    // Заполняем дп внизу

    // вверх

    for (int i = 0; i < n; i++) {

  

        // Максимум из трех секций

        long m1 = 0, m2 = 0, m3 = 0;

  

        for (int j = 0; j < m; j++) {

  

            // Максимум первого раздела

            if ((j / (m / 3)) == 0) {

                m1 = max(m1, arr[i][j]);

            }

  

            // Максимум второго раздела

            else if ((j / (m / 3)) == 1) {

                m2 = max(m2, arr[i][j]);

            }

  

            // Максимум третьего раздела

            else if ((j / (m / 3)) == 2) {

                m3 = max(m3, arr[i][j]);

            }

        }

  

        // Если мы выберем элемент из раздела 1,

        // у нас не может быть выбора из того же раздела

        // в соседних строках

        dp[i + 1][0] = max(dp[i][1], dp[i][2]) + m1;

        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + m2;

        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + m3;

    }

  

    // Выводим максимальную сумму

    cout << max(max(dp[n][0], dp[n][1]), dp[n][2]) << '\n';

}

  
// Код драйвера

int main()

{

  

    long arr[n][m] = { { 1, 3, 5, 2, 4, 6 },

                       { 6, 4, 5, 1, 3, 2 },

                       { 1, 3, 5, 2, 4, 6 },

                       { 6, 4, 5, 1, 3, 2 },

                       { 6, 4, 5, 1, 3, 2 },

                       { 1, 3, 5, 2, 4, 6 } };

  

    maxSum(arr);

  

    return 0;

}

Джава

// Java-программа для вышеуказанного подхода

class GFG

{

  

static int n = 6, m = 6;

  
// Функция для поиска максимального значения

static void maxSum(long arr[][])

{

    // таблица дп

    long [][]dp= new long[n + 1][3];

  

    // Заполняем дп внизу

    // вверх

    for (int i = 0; i < n; i++)

    {

  

        // Максимум из трех секций

        long m1 = 0, m2 = 0, m3 = 0;

  

        for (int j = 0; j < m; j++) 

        {

  

            // Максимум первого раздела

            if ((j / (m / 3)) == 0

            {

                m1 = Math.max(m1, arr[i][j]);

            }

  

            // Максимум второго раздела

            else if ((j / (m / 3)) == 1)

            {

                m2 = Math.max(m2, arr[i][j]);

            }

  

            // Максимум третьего раздела

            else if ((j / (m / 3)) == 2)

            {

                m3 = Math.max(m3, arr[i][j]);

            }

        }

  

        // Если мы выберем элемент из раздела 1,

        // у нас не может быть выбора из того же раздела

        // в соседних строках

        dp[i + 1][0] = Math.max(dp[i][1], dp[i][2]) + m1;

        dp[i + 1][1] = Math.max(dp[i][0], dp[i][2]) + m2;

        dp[i + 1][2] = Math.max(dp[i][1], dp[i][0]) + m3;

    }

  

    // Выводим максимальную сумму

    System.out.print(Math.max(Math.max(dp[n][0], dp[n][1]), dp[n][2]) + "\n");

}

  
// Код драйвера

public static void main(String[] args)

{

  

    long arr[][] = { { 1, 3, 5, 2, 4, 6 },

                    { 6, 4, 5, 1, 3, 2 },

                    { 1, 3, 5, 2, 4, 6 },

                    { 6, 4, 5, 1, 3, 2 },

                    { 6, 4, 5, 1, 3, 2 },

                    { 1, 3, 5, 2, 4, 6 } };

  

    maxSum(arr);

}
}

  
// Этот код предоставлен PrinciRaj1992

python3

# Python3 программа для вышеуказанного подхода

import numpy as np

n = 6; m = 6

  
# Функция поиска максимального значения

def maxSum(arr) :

  

    # Dp table

    dp = np.zeros((n + 1, 3)); 

  

    # Заполните дп в нижней части

    # до манеры

    for i in range(n) :

  

        # Максимум из трех секций

        m1 = 0; m2 = 0; m3 = 0;

          

        for j in range(m) :

              

            # Максимум первого раздела

            if ((j // (m // 3)) == 0) :

                m1 = max(m1, arr[i][j]);

                  

            # Максимум второй секции

            elif ((j // (m // 3)) == 1) :

                m2 = max(m2, arr[i][j]);

                  

            # Максимум третьего раздела

            elif ((j // (m // 3)) == 2) :

                m3 = max(m3, arr[i][j]);

                  

        # Если мы выберем элемент из раздела 1,

        # у нас не может быть выбора из того же раздела

        # в соседних строках

        dp[i + 1][0] = max(dp[i][1], dp[i][2]) + m1;

        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + m2;

        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + m3; 

  

    # Вывести максимальную сумму

    print(max(max(dp[n][0], dp[n][1]), dp[n][2])); 

  
# Код драйвера

if __name__ == "__main__"

  

    arr = [[ 1, 3, 5, 2, 4, 6 ], 

           [ 6, 4, 5, 1, 3, 2 ], 

           [ 1, 3, 5, 2, 4, 6 ], 

           [ 6, 4, 5, 1, 3, 2 ], 

           [ 6, 4, 5, 1, 3, 2 ], 

           [ 1, 3, 5, 2, 4, 6 ]]; 

  

    maxSum(arr); 

      
# Этот код предоставлен AnkitRai01

C #

// C # программа для вышеуказанного подхода

using System;

  

class GFG

{

static int n = 6, m = 6;

  
// Функция для поиска максимального значения

static void maxSum(long [,]arr)

{

    // таблица дп

    long [,]dp = new long[n + 1, 3];

  

    // Заполняем дп внизу

    // вверх

    for (int i = 0; i < n; i++)

    {

  

        // Максимум из трех секций

        long m1 = 0, m2 = 0, m3 = 0;

  

        for (int j = 0; j < m; j++) 

        {

  

            // Максимум первого раздела

            if ((j / (m / 3)) == 0) 

            {

                m1 = Math.Max(m1, arr[i, j]);

            }

  

            // Максимум второго раздела

            else if ((j / (m / 3)) == 1)

            {

                m2 = Math.Max(m2, arr[i, j]);

            }

  

            // Максимум третьего раздела

            else if ((j / (m / 3)) == 2)

            {

                m3 = Math.Max(m3, arr[i, j]);

            }

        }

  

        // Если мы выберем элемент из раздела 1,

        // у нас не может быть выбора из того же раздела

        // в соседних строках

        dp[i + 1, 0] = Math.Max(dp[i, 1], dp[i, 2]) + m1;

        dp[i + 1, 1] = Math.Max(dp[i, 0], dp[i, 2]) + m2;

        dp[i + 1, 2] = Math.Max(dp[i, 1], dp[i, 0]) + m3;

    }

  

    // Выводим максимальную сумму

    Console.Write(Math.Max(Math.Max(dp[n, 0],

                                    dp[n, 1]),

                                    dp[n, 2]) + "\n");

}

  
// Код драйвера

public static void Main(String[] args)

{

    long [,]arr = { { 1, 3, 5, 2, 4, 6 },

                    { 6, 4, 5, 1, 3, 2 },

                    { 1, 3, 5, 2, 4, 6 },

                    { 6, 4, 5, 1, 3, 2 },

                    { 6, 4, 5, 1, 3, 2 },

                    { 1, 3, 5, 2, 4, 6 } };

  

    maxSum(arr);

}
}

  
// Этот код предоставлен 29AjayKumar

Выход:

35

Сложность времени: O (N * M)

Рекомендуемые посты:

Максимизируйте сумму, выбирая элементы из разных разделов матрицы

0.00 (0%) 0 votes