Увеличьте сумму, выбирая элементы из разных разделов матрицы

Опубликовано: 5 Января, 2022

Дана матрица из 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 
 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: проблема может быть решена с использованием решения динамического программирования путем сохранения подзадач и их повторного использования. Создайте массив 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++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
const int n = 6, m = 6;
// Function to find the maximum value
void maxSum( long arr[n][m])
{
// Dp table
long dp[n + 1][3] = { 0 };
// Fill the dp in bottom
// up manner
for ( int i = 0; i < n; i++) {
// Maximum of the three sections
long m1 = 0, m2 = 0, m3 = 0;
for ( int j = 0; j < m; j++) {
// Maximum of the first section
if ((j / (m / 3)) == 0) {
m1 = max(m1, arr[i][j]);
}
// Maximum of the second section
else if ((j / (m / 3)) == 1) {
m2 = max(m2, arr[i][j]);
}
// Maximum of the third section
else if ((j / (m / 3)) == 2) {
m3 = max(m3, arr[i][j]);
}
}
// If we choose element from section 1,
// we cannot have selection from same section
// in adjacent rows
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 the maximum sum
cout << max(max(dp[n][0], dp[n][1]), dp[n][2]) << ' ' ;
}
// Driver code
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 program for the above approach
class GFG
{
static int n = 6 , m = 6 ;
// Function to find the maximum value
static void maxSum( long arr[][])
{
// Dp table
long [][]dp= new long [n + 1 ][ 3 ];
// Fill the dp in bottom
// up manner
for ( int i = 0 ; i < n; i++)
{
// Maximum of the three sections
long m1 = 0 , m2 = 0 , m3 = 0 ;
for ( int j = 0 ; j < m; j++)
{
// Maximum of the first section
if ((j / (m / 3 )) == 0 )
{
m1 = Math.max(m1, arr[i][j]);
}
// Maximum of the second section
else if ((j / (m / 3 )) == 1 )
{
m2 = Math.max(m2, arr[i][j]);
}
// Maximum of the third section
else if ((j / (m / 3 )) == 2 )
{
m3 = Math.max(m3, arr[i][j]);
}
}
// If we choose element from section 1,
// we cannot have selection from same section
// in adjacent rows
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;
}
// Print the maximum sum
System.out.print(Math.max(Math.max(dp[n][ 0 ], dp[n][ 1 ]), dp[n][ 2 ]) + " " );
}
// Driver code
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);
}
}
// This code is contributed by PrinciRaj1992

Python3

# Python3 program for the above approach
import numpy as np
n = 6 ; m = 6 ;
# Function to find the maximum value
def maxSum(arr) :
# Dp table
dp = np.zeros((n + 1 , 3 ));
# Fill the dp in bottom
# up manner
for i in range (n) :
# Maximum of the three sections
m1 = 0 ; m2 = 0 ; m3 = 0 ;
for j in range (m) :
# Maximum of the first section
if ((j / / (m / / 3 )) = = 0 ) :
m1 = max (m1, arr[i][j]);
# Maximum of the second section
elif ((j / / (m / / 3 )) = = 1 ) :
m2 = max (m2, arr[i][j]);
# Maximum of the third section
elif ((j / / (m / / 3 )) = = 2 ) :
m3 = max (m3, arr[i][j]);
# If we choose element from section 1,
# we cannot have selection from same section
# in adjacent rows
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 the maximum sum
print ( max ( max (dp[n][ 0 ], dp[n][ 1 ]), dp[n][ 2 ]));
# Driver code
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);
# This code is contributed by AnkitRai01

C #

// C# program for the above approach
using System;
class GFG
{
static int n = 6, m = 6;
// Function to find the maximum value
static void maxSum( long [,]arr)
{
// Dp table
long [,]dp = new long [n + 1, 3];
// Fill the dp in bottom
// up manner
for ( int i = 0; i < n; i++)
{
// Maximum of the three sections
long m1 = 0, m2 = 0, m3 = 0;
for ( int j = 0; j < m; j++)
{
// Maximum of the first section
if ((j / (m / 3)) == 0)
{
m1 = Math.Max(m1, arr[i, j]);
}
// Maximum of the second section
else if ((j / (m / 3)) == 1)
{
m2 = Math.Max(m2, arr[i, j]);
}
// Maximum of the third section
else if ((j / (m / 3)) == 2)
{
m3 = Math.Max(m3, arr[i, j]);
}
}
// If we choose element from section 1,
// we cannot have selection from same section
// in adjacent rows
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;
}
// Print the maximum sum
Console.Write(Math.Max(Math.Max(dp[n, 0],
dp[n, 1]),
dp[n, 2]) + " " );
}
// Driver code
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);
}
}
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript program for the above approach
const n = 6, m = 6;
// Function to find the maximum value
function maxSum(arr)
{
// Dp table
const dp = new Array(n+1).fill(0).map(() => new Array(3).fill(0));
// Fill the dp in bottom
// up manner
for ( var i = 0; i < n; i++) {
// Maximum of the three sections
var m1 = 0, m2 = 0, m3 = 0;
for ( var j = 0; j < m; j++) {
// Maximum of the first section
if (parseInt(j / (m / 3)) == 0) {
m1 = Math.max(m1, arr[i][j]);
}
// Maximum of the second section
else if (parseInt(j / (m / 3)) == 1) {
m2 = Math.max(m2, arr[i][j]);
}
// Maximum of the third section
else if (parseInt(j / (m / 3)) == 2) {
m3 = Math.max(m3, arr[i][j]);
}
}
// If we choose element from section 1,
// we cannot have selection from same section
// in adjacent rows
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;
}
// Print the maximum sum
document.write( parseInt(Math.max(Math.max(dp[n][0], dp[n][1]), dp[n][2])) + "<br>" );
}
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);
//This code is contributed by SoumikMondal
</script>
Выход:

35

Technical Scripter Олимпиады по программированию

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Количество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023