Dada una array G[][] de dimensiones N × M , compuesta por números enteros positivos, la tarea es seleccionar X elementos de la array que tengan la suma máxima considerando la condición de que G[i][j] solo se puede seleccionar de la array a menos que se seleccionen todos los elementos G[i][k] , donde 0 ≤ k < j , es decir, el j -ésimo elemento en la actual i -ésima fila puede seleccionarse todos sus elementos precedentes de la actual i -ésima fila ya han sido seleccionados .
Ejemplos:
Entrada: N = 4, M = 4, X = 6, G[][] = {{3, 2, 6, 1}, {1, 9, 2, 4}, {4, 1, 3, 9} , {3, 8, 2, 1}}
Salida: 28
Explicación:
Seleccionar el primer elemento de la primera fila = 3
Seleccionar los dos primeros elementos de la segunda fila = 1 + 9 = 10
Seleccionar el primer elemento de la tercera fila = 4
Seleccionando los primeros dos elementos de la 4ta fila = 3 + 8 = 11
Por lo tanto, los elementos seleccionados son {G[0][0], G[1][0], G[1][1], G[2 ][0], G[3][0], G[3][1]}
Por lo tanto, la suma de los elementos seleccionados es = 3 + 10 + 4 + 11 = 28Entrada: N = 2, M = 4, X = 4, G[][] = {{10, 10, 100, 30}, {80, 50, 10, 50}}
Salida: 200
Enfoque ingenuo: el enfoque más simple para resolver este problema es calcular la suma de todas las M selecciones posibles y encontrar la suma máxima entre ellas.
Complejidad de Tiempo: O(N M )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante la programación dinámica . Los estados considerables son:
- Número de filas seleccionadas: i .
- Número de elementos seleccionados: j .
Inicialice una array dp[][] tal que dp[i][j] almacene la suma máxima posible que se puede obtener seleccionando j elementos de las primeras i filas.
La transición para dp[][] es la siguiente:
=
donde prefsum[i][x] es la suma de los primeros x elementos en la i -ésima fila de la array.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++14 program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
int n, m, X;
// Function to calculate the maximum
// possible sum by selecting X elements
// from the Matrix
int maxSum(vector<vector<int>> grid)
{
// Generate prefix sum of the matrix
vector<vector<int>> prefsum(n, vector<int>(m));
for(int i = 0; i < n; i++)
{
for(int x = 0; x < m; x++)
{
if (x == 0)
prefsum[i][x] = grid[i][x];
else
prefsum[i][x] = prefsum[i][x - 1] +
grid[i][x];
}
}
vector<vector<int>> dp(n, vector<int>(X + 1, INT_MIN));
// Maximum possible sum by selecting
// 0 elements from the first i rows
for(int i = 0; i < n; i++)
dp[i][0] = 0;
// If a single row is present
for(int i = 1; i <= min(m, X); ++i)
{
dp[0][i] = dp[0][i - 1] +
grid[0][i - 1];
}
for(int i = 1; i < n; ++i)
{
for(int j = 1; j <= X; ++j)
{
// If elements from the
// current row is not selected
dp[i][j] = dp[i - 1][j];
// Iterate over all possible
// selections from current row
for(int x = 1; x <= min(j, m); x++)
{
dp[i][j] = max(dp[i][j],
dp[i - 1][j - x] +
prefsum[i][x - 1]);
}
}
}
// Return maximum possible sum
return dp[n - 1][X];
}
// Driver code
int main()
{
n = 4;
m = 4;
X = 6;
vector<vector<int>> grid = { { 3, 2, 6, 1 },
{ 1, 9, 2, 4 },
{ 4, 1, 3, 9 },
{ 3, 8, 2, 1 } };
int ans = maxSum(grid);
cout << (ans);
return 0;
}
// This code is contributed by mohit kumar 29
Java
// Java program to implement
// the above approach
import java.util.*;
import java.io.*;
class GFG {
static int n, m, X;
// Function to calculate the maximum
// possible sum by selecting X elements
// from the Matrix
public static int maxSum(int[][] grid)
{
// Generate prefix sum of the matrix
int prefsum[][] = new int[n][m];
for (int i = 0; i < n; i++) {
for (int x = 0; x < m; x++) {
if (x == 0)
prefsum[i][x] = grid[i][x];
else
prefsum[i][x]
= prefsum[i][x - 1] + grid[i][x];
}
}
int dp[][] = new int[n][X + 1];
// Initialize dp[][]
for (int dpp[] : dp)
Arrays.fill(dpp, Integer.MIN_VALUE);
// Maximum possible sum by selecting
// 0 elements from the first i rows
for (int i = 0; i < n; i++)
dp[i][0] = 0;
// If a single row is present
for (int i = 1; i <= Math.min(m, X); ++i) {
dp[0][i] = dp[0][i - 1] + grid[0][i - 1];
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= X; ++j) {
// If elements from the
// current row is not selected
dp[i][j] = dp[i - 1][j];
// Iterate over all possible
// selections from current row
for (int x = 1; x <= Math.min(j, m);
x++) {
dp[i][j]
= Math.max(dp[i][j],
dp[i - 1][j - x]
+ prefsum[i][x - 1]);
}
}
}
// Return maximum possible sum
return dp[n - 1][X];
}
// Driver Code
public static void main(String[] args)
{
n = 4;
m = 4;
X = 6;
int grid[][] = { { 3, 2, 6, 1 },
{ 1, 9, 2, 4 },
{ 4, 1, 3, 9 },
{ 3, 8, 2, 1 } };
int ans = maxSum(grid);
System.out.println(ans);
}
}
Python3
# Python3 program to implement # the above approach import sys # Function to calculate the maximum # possible sum by selecting X elements # from the Matrix def maxSum(grid): # Generate prefix sum of the matrix prefsum = [[0 for x in range(m)] for y in range(m)] for i in range(n): for x in range(m): if (x == 0): prefsum[i][x] = grid[i][x] else: prefsum[i][x] = (prefsum[i][x - 1] + grid[i][x]) dp = [[-sys.maxsize - 1 for x in range(X + 1)] for y in range(n)] # Maximum possible sum by selecting # 0 elements from the first i rows for i in range(n): dp[i][0] = 0 # If a single row is present for i in range(1, min(m, X)): dp[0][i] = (dp[0][i - 1] + grid[0][i - 1]) for i in range(1, n): for j in range(1, X + 1): # If elements from the # current row is not selected dp[i][j] = dp[i - 1][j] # Iterate over all possible # selections from current row for x in range(1, min(j, m) + 1): dp[i][j] = max(dp[i][j], dp[i - 1][j - x] + prefsum[i][x - 1]) # Return maximum possible sum return dp[n - 1][X] # Driver Code if __name__ == "__main__": n = 4 m = 4 X = 6 grid = [ [ 3, 2, 6, 1 ], [ 1, 9, 2, 4 ], [ 4, 1, 3, 9 ], [ 3, 8, 2, 1 ] ] ans = maxSum(grid) print(ans) # This code is contributed by chitranayal
C#
// C# program to implement
// the above approach
using System;
class GFG{
static int n, m, X;
// Function to calculate the maximum
// possible sum by selecting X elements
// from the Matrix
public static int maxSum(int[,] grid)
{
// Generate prefix sum of the matrix
int [,]prefsum = new int[n, m];
for(int i = 0; i < n; i++)
{
for(int x = 0; x < m; x++)
{
if (x == 0)
prefsum[i, x] = grid[i, x];
else
prefsum[i, x] = prefsum[i, x - 1] +
grid[i, x];
}
}
int [,]dp = new int[n, X + 1];
// Initialize [,]dp
for(int i = 1; i < n; i++)
for(int j = 1; j <= X; ++j)
dp[i, j] = int.MinValue;
// Maximum possible sum by selecting
// 0 elements from the first i rows
for(int i = 0; i < n; i++)
dp[i, 0] = 0;
// If a single row is present
for(int i = 1; i <= Math.Min(m, X); ++i)
{
dp[0, i] = dp[0, i - 1] + grid[0, i - 1];
}
for(int i = 1; i < n; ++i)
{
for(int j = 1; j <= X; ++j)
{
// If elements from the
// current row is not selected
dp[i, j] = dp[i - 1, j];
// Iterate over all possible
// selections from current row
for(int x = 1; x <= Math.Min(j, m); x++)
{
dp[i, j] = Math.Max(dp[i, j],
dp[i - 1, j - x] +
prefsum[i, x - 1]);
}
}
}
// Return maximum possible sum
return dp[n - 1, X];
}
// Driver Code
public static void Main(String[] args)
{
n = 4;
m = 4;
X = 6;
int [,]grid = { { 3, 2, 6, 1 },
{ 1, 9, 2, 4 },
{ 4, 1, 3, 9 },
{ 3, 8, 2, 1 } };
int ans = maxSum(grid);
Console.WriteLine(ans);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
let n, m, X;
// Function to calculate the maximum
// possible sum by selecting X elements
// from the Matrix
function maxSum(grid)
{
// Generate prefix sum of the matrix
let prefsum = new Array(n);
// Loop to create 2D array using 1D array
for (var i = 0; i < prefsum.length; i++) {
prefsum[i] = new Array(2);
}
for (let i = 0; i < n; i++) {
for (let x = 0; x < m; x++) {
if (x == 0)
prefsum[i][x] = grid[i][x];
else
prefsum[i][x]
= prefsum[i][x - 1] + grid[i][x];
}
}
let dp = new Array(n);
// Loop to create 2D array using 1D array
for (var i = 0; i < dp.length; i++) {
dp[i] = new Array(2);
}
for (var i = 0; i < n; i++) {
for (var j = 0; j < X+1; j++) {
dp[i][j] = 0;
}
}
// Maximum possible sum by selecting
// 0 elements from the first i rows
for (let i = 0; i < n; i++)
dp[i][0] = 0;
// If a single row is present
for (let i = 1; i <= Math.min(m, X); ++i) {
dp[0][i] = dp[0][i - 1] + grid[0][i - 1];
}
for (let i = 1; i < n; ++i) {
for (let j = 1; j <= X; ++j) {
// If elements from the
// current row is not selected
dp[i][j] = dp[i - 1][j];
// Iterate over all possible
// selections from current row
for (let x = 1; x <= Math.min(j, m);
x++) {
dp[i][j]
= Math.max(dp[i][j],
dp[i - 1][j - x]
+ prefsum[i][x - 1]);
}
}
}
// Return maximum possible sum
return dp[n - 1][X];
}
// Driver Code
n = 4;
m = 4;
X = 6;
let grid = [[ 3, 2, 6, 1 ],
[ 1, 9, 2, 4 ],
[ 4, 1, 3, 9 ],
[ 3, 8, 2, 1 ]];
let ans = maxSum(grid);
document.write(ans);
</script>
28
Complejidad temporal: O(N*M*X)
Espacio auxiliar: O(N*M)