Dada una array 2D arr[][] de tamaño N * M y un número entero K , la tarea es seleccionar K elementos con la suma máxima posible de modo que si se selecciona un elemento arr[i][j] , entonces todos los elementos de la i -ésima fila presente antes de la j -ésima columna debe seleccionarse.
Ejemplos:
Entrada: arr[][] = {{10, 10, 100, 30}, {80, 50, 10, 50}}, K = 5
Salida: 250
Explicación:
Selección de los primeros 3 elementos de la primera fila, suma = 10 + 10 + 100 = 120
Seleccionando los 2 primeros elementos de la segunda fila, suma = 80 + 50 = 130
Por lo tanto, la suma máxima = 120 + 130 = 250.Entrada: arr[][] = {{30, 10, 110, 13}, {810, 152, 12, 5}, {124, 24, 54, 124}}, K = 6
Salida: 1288
Explicación:
Seleccionar primero 2 elementos de la segunda fila, suma = 810 + 152 = 962
Seleccionando los 4 elementos de la tercera fila, suma = 124 + 24 + 54 + 124 = 326
Por lo tanto, la suma máxima = 962 + 326 = 1288
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subconjuntos posibles de tamaño K a partir de la array dada en función de la restricción especificada y calcular la suma máxima posible de estos subconjuntos.
Complejidad de tiempo: O((N*M)!/(K!)*(N*M – K)!)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de la programación dinámica . La idea es encontrar la suma máxima de seleccionar i elementos hasta la fila j de la array 2D arr[][] . La array auxiliar dp[i][j + 1] almacena la suma máxima de la selección de i elementos hasta la j -ésima fila de la array arr[][] . Siga los pasos a continuación para resolver el problema:
- Inicialice una tabla dp[][] de tamaño (K+1)*(N+1) e inicialice dp[0][i] como 0 , ya que ningún elemento tiene una suma igual a 0 .
- Inicialice dp[i][0] como 0 , ya que no hay elementos para seleccionar.
- Itere sobre el rango [0, K] usando dos bucles anidados y [0, N] usando las variables i y j respectivamente:
- Inicialice una variable, digamos sum como 0 , para realizar un seguimiento de la suma acumulada de elementos en la j -ésima fila de arr[][] .
- Inicialice maxSum como dp[i][j] , si no es necesario seleccionar ningún elemento de la fila j de arr[][] .
- Iterar con k como 1 hasta k > M o k > i :
- Incremento suma += comprar[j][k – 1] .
- Almacene el máximo de maxSum y (sum + dp[i – k][j]) existentes en maxSum .
- Almacene dp[i][j + 1] como el valor de maxSum .
- Imprime el valor dp[K][N] como la suma máxima de K elementos hasta (N – 1) la fila de la array arr[][] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to return the maximum
// of two elements
int max(int a, int b)
{
return a > b ? a : b;
}
// Function to find the maximum sum
// of selecting K elements from
// the given 2D array arr[][]
int maximumsum(int arr[][4], int K,
int N, int M)
{
int sum = 0, maxSum;
int i, j, k;
// dp table of size (K+1)*(N+1)
int dp[K + 1][N + 1];
// Initialize dp[0][i] = 0
for (i = 0; i <= N; i++)
dp[0][i] = 0;
// Initialize dp[i][0] = 0
for (i = 0; i <= K; i++)
dp[i][0] = 0;
// Selecting i elements
for (i = 1; i <= K; i++) {
// Select i elements till jth row
for (j = 0; j < N; j++) {
// dp[i][j+1] is the maximum
// of selecting i elements till
// jth row
// sum = 0, to keep track of
// cumulative elements sum
sum = 0;
maxSum = dp[i][j];
// Traverse arr[j][k] until
// number of elements until k>i
for (k = 1; k <= M && k <= i; k++) {
// Select arr[j][k - 1]th item
sum += arr[j][k - 1];
maxSum
= max(maxSum,
sum + dp[i - k][j]);
}
// Store the maxSum in dp[i][j+1]
dp[i][j + 1] = maxSum;
}
}
// Return the maximum sum
return dp[K][N];
}
// Driver Code
int main()
{
int arr[][4] = { { 10, 10, 100, 30 },
{ 80, 50, 10, 50 } };
int N = 2, M = 4;
int K = 5;
// Function Call
cout << maximumsum(arr, K, N, M);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to return the maximum
// of two elements
static int max(int a, int b)
{
return a > b ? a : b;
}
// Function to find the maximum sum
// of selecting K elements from
// the given 2D array arr[][]
static int maximumsum(int arr[][], int K,
int N, int M)
{
int sum = 0, maxSum;
int i, j, k;
// dp table of size (K+1)*(N+1)
int[][] dp = new int[K + 1][N + 1];
// Initialize dp[0][i] = 0
for(i = 0; i <= N; i++)
dp[0][i] = 0;
// Initialize dp[i][0] = 0
for(i = 0; i <= K; i++)
dp[i][0] = 0;
// Selecting i elements
for(i = 1; i <= K; i++)
{
// Select i elements till jth row
for(j = 0; j < N; j++)
{
// dp[i][j+1] is the maximum
// of selecting i elements till
// jth row
// sum = 0, to keep track of
// cumulative elements sum
sum = 0;
maxSum = dp[i][j];
// Traverse arr[j][k] until
// number of elements until k>i
for(k = 1; k <= M && k <= i; k++)
{
// Select arr[j][k - 1]th item
sum += arr[j][k - 1];
maxSum = Math.max(maxSum,
sum + dp[i - k][j]);
}
// Store the maxSum in dp[i][j+1]
dp[i][j + 1] = maxSum;
}
}
// Return the maximum sum
return dp[K][N];
}
// Driver Code
public static void main(String[] args)
{
int arr[][] = { { 10, 10, 100, 30 },
{ 80, 50, 10, 50 } };
int N = 2, M = 4;
int K = 5;
// Function Call
System.out.print(maximumsum(arr, K, N, M));
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python program for the above approach import math; # Function to return the maximum # of two elements def max(a, b): if(a > b): return a; else: return b; # Function to find the maximum sum # of selecting K elements from # the given 2D array arr def maximumsum(arr, K, N, M): sum = 0; maxSum = 0; # dp table of size (K+1)*(N+1) dp = [[0 for i in range(N + 1)] for j in range(K + 1)] # Initialize dp[0][i] = 0 for i in range(0, N + 1): dp[0][i] = 0; # Initialize dp[i][0] = 0 for i in range(0, K + 1): dp[i][0] = 0; # Selecting i elements for i in range(1, K + 1): # Select i elements till jth row for j in range(0, N): # dp[i][j+1] is the maximum # of selecting i elements till # jth row # sum = 0, to keep track of # cumulative elements sum sum = 0; maxSum = dp[i][j]; # Traverse arr[j][k] until # number of elements until k>i for k in range(1, i + 1): if(k > M): break; # Select arr[j][k - 1]th item sum += arr[j][k - 1]; maxSum = max(maxSum, sum + dp[i - k][j]); # Store the maxSum in dp[i][j+1] dp[i][j + 1] = maxSum; # Return the maximum sum return dp[K][N]; # Driver Code if __name__ == '__main__': arr = [[10, 10, 100, 30], [80, 50, 10, 50]]; N = 2; M = 4; K = 5; # Function Call print(maximumsum(arr, K, N, M)); # This code is contributed by 29AjayKumar
C#
// C# program for the above approach
using System;
class GFG{
// Function to return the maximum
// of two elements
static int max(int a, int b)
{
return a > b ? a : b;
}
// Function to find the maximum sum
// of selecting K elements from
// the given 2D array [,]arr
static int maximumsum(int [,]arr, int K,
int N, int M)
{
int sum = 0, maxSum;
int i, j, k;
// dp table of size (K+1)*(N+1)
int[,] dp = new int[K + 1, N + 1];
// Initialize dp[0,i] = 0
for(i = 0; i <= N; i++)
dp[0, i] = 0;
// Initialize dp[i,0] = 0
for(i = 0; i <= K; i++)
dp[i, 0] = 0;
// Selecting i elements
for(i = 1; i <= K; i++)
{
// Select i elements till jth row
for(j = 0; j < N; j++)
{
// dp[i,j+1] is the maximum
// of selecting i elements till
// jth row
// sum = 0, to keep track of
// cumulative elements sum
sum = 0;
maxSum = dp[i, j];
// Traverse arr[j,k] until
// number of elements until k>i
for(k = 1; k <= M && k <= i; k++)
{
// Select arr[j,k - 1]th item
sum += arr[j, k - 1];
maxSum = Math.Max(maxSum,
sum + dp[i - k, j]);
}
// Store the maxSum in dp[i,j+1]
dp[i, j + 1] = maxSum;
}
}
// Return the maximum sum
return dp[K, N];
}
// Driver Code
public static void Main(String[] args)
{
int [,]arr = { { 10, 10, 100, 30 },
{ 80, 50, 10, 50 } };
int N = 2, M = 4;
int K = 5;
// Function Call
Console.Write(maximumsum(arr, K, N, M));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to return the maximum
// of two elements
function max(a, b)
{
return a > b ? a : b;
}
// Function to find the maximum sum
// of selecting K elements from
// the given 2D array arr[][]
function maximumsum(arr, K,
N, M)
{
let sum = 0, maxSum;
let i, j, k;
// dp table of size (K+1)*(N+1)
let dp = new Array(K + 1);
// Loop to create 2D array using 1D array
for ( i = 0; i < dp.length; i++) {
dp[i] = new Array(2);
}
// Initialize dp[0][i] = 0
for(i = 0; i <= N; i++)
dp[0][i] = 0;
// Initialize dp[i][0] = 0
for(i = 0; i <= K; i++)
dp[i][0] = 0;
// Selecting i elements
for(i = 1; i <= K; i++)
{
// Select i elements till jth row
for(j = 0; j < N; j++)
{
// dp[i][j+1] is the maximum
// of selecting i elements till
// jth row
// sum = 0, to keep track of
// cumulative elements sum
sum = 0;
maxSum = dp[i][j];
// Traverse arr[j][k] until
// number of elements until k>i
for(k = 1; k <= M && k <= i; k++)
{
// Select arr[j][k - 1]th item
sum += arr[j][k - 1];
maxSum = Math.max(maxSum,
sum + dp[i - k][j]);
}
// Store the maxSum in dp[i][j+1]
dp[i][j + 1] = maxSum;
}
}
// Return the maximum sum
return dp[K][N];
}
// Driver code
let arr = [[ 10, 10, 100, 30 ],
[ 80, 50, 10, 50 ]];
let N = 2, M = 4;
let K = 5;
// Function Call
document.write(maximumsum(arr, K, N, M));
// This code is contributed by souravghosh0416.
</script>
Producción:
250
Complejidad temporal: O(K*N*M)
Espacio auxiliar: O(K*N)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA