Dados dos números enteros N y M , donde N es el número de casillas colocadas en una fila y M es el número de colores de diamantes que se distribuyen en estas casillas de modo que cada casilla contenga al menos 1 diamante. Cada diamante tiene un color y un valor representado por una array M * N donde mat[i][j] denota el número de diamantes de color i en el j -ésimo cuadro. La tarea es tomar exactamente un tipo de diamante de color de cada caja de manera que el valor total de los diamantes elegidos sea el máximo y los diamantes tomados de las cajas adyacentes sean de un color diferente. Si no es posible satisfacer la condición, imprima-1 .
Ejemplos:
Entrada: mat[][] = {
{10, 2, 20, 0},
{0, 0, 5, 0},
{0, 0, 0, 6},
{4, 0, 11, 5},
{ 0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}}
Salida: 23
Explicación: Del cuadro 1, podemos elegir 10 diamantes de Color1 o 4 diamantes de Color4. Pero dado que del cuadro 2, tenemos que elegir 2 diamantes de Color 1, por lo tanto, elija 4 diamantes de Color 4 del cuadro 1.
Del mismo modo, para maximizar el número de diamantes, elija 11 diamantes de Color 4 del cuadro 3 y 6 diamantes de Color 3 del cuadro 4.
El total de diamantes elegidos = 4 + 2 + 11 + 6 = 23, que es el número máximo posible.Entrada: mat[][] = {
{1, 0, 0},
{0, 0, 5},
{0, 11, 5},
{0, 0, 0},
{0, 0, 0},
{ 0, 0, 0},
{0, 0, 0}}
Salida: 16
Explicación: Elegimos 1 de la 1ª casilla de Color1, 11 de la 2ª casilla de Color3 y 5 de la 3ª casilla de Color2.
Acercarse:
- La programación dinámica se puede utilizar para resolver este problema.
- Haga una array 2-D de tamaño M x N y la definición será, eligiendo el i -ésimo color de la j -ésima columna, cuál es el valor máximo que se puede obtener.
- La relación de recurrencia será dp[i][j] = arr[i][j] + max of (dp[1…M][i-1]) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximized value
int maxSum(vector<vector<int> > arr)
{
// Number of rows and columns
int m = (int)arr.size();
int n = (int)arr[0].size() - 1;
// Creating the Dp array
int dp[m][n + 1];
// memset(arr, 0, sizeof(arr));
memset(dp, 0, sizeof(dp));
// Populating the first column
for (int i = 1; i < m; ++i)
dp[i][1] = arr[i][1];
for (int i = 1; i < n + 1; ++i) {
// Iterating over all the rows
for (int j = 1; j < m; ++j) {
int mx = 0;
// Getting the (i-1)th max value
for (int k = 1; k < m; ++k) {
if (k != j) {
if (dp[k][i - 1] > mx) {
mx = dp[k][i - 1];
}
}
}
// Adding it to the current cell
if (mx and arr[j][i]) {
dp[j][i] = arr[j][i] + mx;
}
}
}
// Getting the max sum
// from the last column
int ans = -1;
for (int i = 1; i <= m; ++i) {
if (dp[i][n])
ans = max(ans, dp[i][n]);
}
return ans;
}
// Driver code
int main()
{
// Columns are indexed 1-based
vector<vector<int> > arr = {
{ 0, 0, 0, 0, 0 },
{ 0, 10, 2, 20, 0 },
{ 0, 0, 0, 5, 0 },
{ 0, 0, 0, 0, 6 },
{ 0, 4, 0, 11, 5 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 }
};
cout << maxSum(arr);
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
import java.util.*;
class GFG{
// Function to return the maximized value
static int maxSum(int[][] arr)
{
// Number of rows and columns
int m = (int)arr.length;
int n = (int)arr[0].length - 1;
// Creating the Dp array
int[][] dp = new int[m + 1][n + 2];
// memset(arr, 0, sizeof(arr));
for(int i = 0; i <= m; i++)
{
for(int j = 0; j <= n + 1; j++)
{
dp[i][j] = 0;
}
}
// Populating the first column
for(int i = 1; i < m; ++i)
dp[i][1] = arr[i][1];
for(int i = 1; i < n + 1; ++i)
{
// Iterating over all the rows
for(int j = 1; j < m; ++j)
{
int mx = 0;
// Getting the (i-1)th max value
for(int k = 1; k < m; ++k)
{
if (k != j)
{
if (dp[k][i - 1] > mx)
{
mx = dp[k][i - 1];
}
}
}
// Adding it to the current cell
if (mx != 0 && arr[j][i] != 0)
{
dp[j][i] = arr[j][i] + mx;
}
}
}
// Getting the max sum
// from the last column
int ans = -1;
for(int i = 1; i <= m; ++i)
{
if ((dp[i][n]) != 0)
ans = Math.max(ans, dp[i][n]);
}
return ans;
}
// Driver code
public static void main(String[] args)
{
// Columns are indexed 1-based
int[][] arr = { { 0, 0, 0, 0, 0 },
{ 0, 10, 2, 20, 0 },
{ 0, 0, 0, 5, 0 },
{ 0, 0, 0, 0, 6 },
{ 0, 4, 0, 11, 5 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 } };
System.out.println(maxSum(arr));
}
}
// This code is contributed by sanjoy_62
Python3
# Python 3 implementation of the approach # Function to return the maximized value def maxSum(arr): # Number of rows and columns m = len(arr) n = len(arr[0]) - 1 # Creating the Dp array dp = [[0 for i in range(n+1)] for j in range(m)] # Populating the first column for i in range(1,m,1): dp[i][1] = arr[i][1] for i in range(1,n + 1,1): # Iterating over all the rows for j in range(1,m,1): mx = 0 # Getting the (i-1)th max value for k in range(1,m,1): if (k != j): if (dp[k][i - 1] > mx): mx = dp[k][i - 1] # Adding it to the current cell if (mx and arr[j][i]): dp[j][i] = arr[j][i] + mx # Getting the max sum # from the last column ans = -1 for i in range(1,m,1): if (dp[i][n]): ans = max(ans, dp[i][n]) return ans # Driver code if __name__ == '__main__': # Columns are indexed 1-based arr = [[0, 0, 0, 0, 0], [0, 10, 2, 20, 0], [0, 0, 0, 5, 0], [0, 0, 0, 0, 6], [0, 4, 0, 11, 5], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] print(maxSum(arr)) # This code is contributed by bgangwar59.
C#
// C# implementation of the approach
using System;
public class GFG
{
// Function to return the maximized value
static int maxSum(int[,] arr)
{
// Number of rows and columns
int m = (int)arr.GetLength(0);
int n = (int)arr.GetLength(1) - 1;
// Creating the Dp array
int[,] dp = new int[m + 1,n + 2];
// memset(arr, 0, sizeof(arr));
for(int i = 0; i <= m; i++)
{
for(int j = 0; j <= n + 1; j++)
{
dp[i,j] = 0;
}
}
// Populating the first column
for(int i = 1; i < m; ++i)
dp[i,1] = arr[i,1];
for(int i = 1; i < n + 1; ++i)
{
// Iterating over all the rows
for(int j = 1; j < m; ++j)
{
int mx = 0;
// Getting the (i-1)th max value
for(int k = 1; k < m; ++k)
{
if (k != j)
{
if (dp[k,i - 1] > mx)
{
mx = dp[k,i - 1];
}
}
}
// Adding it to the current cell
if (mx != 0 && arr[j,i] != 0)
{
dp[j,i] = arr[j,i] + mx;
}
}
}
// Getting the max sum
// from the last column
int ans = -1;
for(int i = 1; i <= m; ++i)
{
if ((dp[i,n]) != 0)
ans = Math.Max(ans, dp[i,n]);
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
// Columns are indexed 1-based
int[,] arr = { { 0, 0, 0, 0, 0 },
{ 0, 10, 2, 20, 0 },
{ 0, 0, 0, 5, 0 },
{ 0, 0, 0, 0, 6 },
{ 0, 4, 0, 11, 5 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 } };
Console.WriteLine(maxSum(arr));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript implementation of the approach
// Function to return the maximized value
function maxSum(arr)
{
// Number of rows and columns
let m = arr.length;
let n = arr[0].length - 1;
// Creating the Dp array
let dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
// Populating the first column
for (let i = 1; i < m; ++i) dp[i][1] = arr[i][1];
for (let i = 1; i < n + 1; ++i) {
// Iterating over all the rows
for (let j = 1; j < m; ++j) {
let mx = 0;
// Getting the (i-1)th max value
for (let k = 1; k < m; ++k) {
if (k != j) {
if (dp[k][i - 1] > mx) {
mx = dp[k][i - 1];
}
}
}
// Adding it to the current cell
if (mx && arr[j][i]) {
dp[j][i] = arr[j][i] + mx;
}
}
}
// Getting the max sum
// from the last column
let ans = -1;
for (let i = 1; i <= m; ++i) {
if (dp[i][n]) {ans = Math.max(ans, dp[i][n])};
}
return ans;
}
// Driver code
// Columns are indexed 1-based
let arr = [
[0, 0, 0, 0, 0],
[0, 10, 2, 20, 0],
[0, 0, 0, 5, 0],
[0, 0, 0, 0, 6],
[0, 4, 0, 11, 5],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
];
document.write(maxSum(arr));
// This code is contributed by gfgking.
</script>
Producción:
23