Dadas S pilas de longitud M , la tarea es maximizar la suma de elementos en la parte superior de cada pila sacando como máximo N elementos.
Ejemplo:
Entrada: S = 1, N = 3, pilas = { 5, 1, 2, 8, 9 }
Salida: 8
Explicación:
Se pueden eliminar un máximo de 3 elementos.
El elemento actual en la parte superior de la pila es 5.
Al eliminar 5, el nuevo elemento en la parte superior es 1.
Al eliminar 1, el nuevo elemento en la parte superior es 2.
Al eliminar 2, el nuevo elemento en la parte superior top es 8.
No se permiten más operaciones emergentes.
Por lo tanto, el valor máximo posible en la parte superior de la pila es 8.
Entrada: S = 2, N = 2, pilas = { { 2, 6, 4, 5}, {1, 6, 15, 10} }
Salida: 17
Explicación:
Suma actual de los elementos en la parte superior = 2 + 1 = 3.
Sacar 1 de la parte superior de la segunda pila solo hace la suma 8 (5 + 2 = 8)
Sacar 2 de la parte superior de la segunda pila solo hace la suma 7 (6 + 1).
Sacar 1 y 2 de la parte superior de cada pila hace que la suma sea 12 (6 + 6).
Sacar 2 y 6 de la primera pila hace que la suma sea 5 (4 + 1).
Sacando 1 y 6 de la segunda pila deja 15 como el elemento en la parte superior.
Por lo tanto, la suma de los elementos en la parte superior de las dos pilas se maximiza (15 + 2 = 17).
Enfoque: este problema se puede reducir a un problema de mochila 0/1 . Para resolver el problema, siga los pasos a continuación:
- Cree una tabla 2D dp[][] con (S + 1) filas y (N + 1) columnas. En cada índice dp[i][j] , almacene la suma máxima posible al colocar j elementos en la i -ésima pila.
- Inicialice todos los índices dp[][] en 0.
- Iterar sobre cada pila desde i = 0 hasta S – 1
- Ahora, para cada i -ésima pila, calcule la suma máxima posible haciendo estallar j (1 a N) elementos.
- Estos elementos j se pueden seleccionar de todas las pilas i ya visitadas. Por lo tanto, dp[i+1][j] almacena el máximo de pilas[i][k] + dp[i][j – k] para todos los valores de k que van desde 0 hasta min(j, tamaño de la pila) . La relación stacks[i][k] + dp[i][jk] denota la suma obtenida al extraer k elementos de la i -ésima pila actual y la suma máxima posible al extraer j – k elementos de las pilas ya visitadas.
- Una vez que haya terminado para todas las pilas i , encuentre el máximo de dp[S][i] para todas las i en el rango [1, N – 1] .
- El valor máximo obtenido en el paso anterior es la respuesta requerida.
El siguiente código es la implementación del enfoque anterior:
C++
// C++ Program to maximize the // sum of top of the stack // values of S stacks by popping // at most N elements #include <bits/stdc++.h> using namespace std; // Function for computing the // maximum sum at the top of // the stacks after popping at // most N elements from S stack int maximumSum(int S, int M, int N, vector<vector<int> >& stacks) { // Constructing a dp matrix // of dimensions (S+1) x (N+1) int dp[S + 1][N + 1]; // Initialize all states memset(dp, INT_MIN, sizeof(dp)); // Loop over all i stacks for (int i = 0; i < S; i++) { for (int j = 0; j <= N; j++) { for (int k = 0; k <= min(j, M); k++) { // Store the maximum of // popping j elements // up to the current stack // by popping k elements // from current stack and // j - k elements from all // previous stacks combined dp[i + 1][j] = max(dp[i + 1][j], stacks[i][k] + dp[i][j - k]); } } } // Store the maximum sum of // popping N elements across // all stacks int result = INT_MIN; for (int i = 0; i <= N; i++) { result = max(result, dp[S][i]); } // dp[S][N] has the maximum sum return result; } // Driver Program int main() { // Number of stacks int S = 2; // Length of each stack int M = 4; vector<vector<int> > stacks = { { 2, 6, 4, 5 }, { 1, 6, 15, 10 } }; // Maximum elements that // can be popped int N = 3; cout << maximumSum(S, M, N, stacks); return 0; }
Java
// Java Program to maximize the // sum of top of the stack // values of S stacks by popping // at most N elements import java.util.*; class GFG{ // Function for computing the // maximum sum at the top of // the stacks after popping at // most N elements from S stack static int maximumSum(int S, int M, int N, int [][]stacks) { // Constructing a dp matrix // of dimensions (S+1) x (N+1) int [][]dp = new int[S + 1][N + 1]; // Loop over all i stacks for (int i = 0; i < S; i++) { for (int j = 0; j <= N; j++) { for (int k = 0; k <= Math.min(j, M); k++) { // Store the maximum of // popping j elements // up to the current stack // by popping k elements // from current stack and // j - k elements from all // previous stacks combined dp[i + 1][j] = Math.max(dp[i + 1][j], stacks[i][k] + dp[i][j - k]); } } } // Store the maximum sum of // popping N elements across // all stacks int result = Integer.MIN_VALUE; for (int i = 0; i <= N; i++) { result = Math.max(result, dp[S][i]); } // dp[S][N] has the maximum sum return result; } // Driver Program public static void main(String[] args) { // Number of stacks int S = 2; // Length of each stack int M = 4; int [][]stacks = {{ 2, 6, 4, 5 }, { 1, 6, 15, 10 }}; // Maximum elements that // can be popped int N = 3; System.out.print(maximumSum(S, M, N, stacks)); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program to maximize the # sum of top of the stack values # of S stacks by popping at most # N element import sys # Function for computing the # maximum sum at the top of # the stacks after popping at # most N elements from S stack def maximumSum(S, M, N, stacks): # Constructing a dp matrix # of dimensions (S+1) x (N+1) dp = [[0 for x in range(N + 1)] for y in range(S + 1)] # Loop over all i stacks for i in range(S): for j in range(N + 1): for k in range(min(j, M) + 1): # Store the maximum of # popping j elements # up to the current stack # by popping k elements # from current stack and # j - k elements from all # previous stacks combined dp[i + 1][j] = max(dp[i + 1][j], stacks[i][k] + dp[i][j - k]) # Store the maximum sum of # popping N elements across # all stacks result = -sys.maxsize - 1 for i in range(N + 1): result = max(result, dp[S][i]) # dp[S][N] has the maximum sum return result # Driver code if __name__ == "__main__": # Number of stacks S = 2 # Length of each stack M = 4 stacks = [ [ 2, 6, 4, 5 ], [ 1, 6, 15, 10 ] ] # Maximum elements that # can be popped N = 3 print(maximumSum(S, M, N, stacks)) # This code is contributed by chitranayal
C#
// C# program to maximize the sum // of top of the stack values of // S stacks by popping at most N // elements using System; class GFG{ // Function for computing the // maximum sum at the top of // the stacks after popping at // most N elements from S stack static int maximumSum(int S, int M, int N, int [,]stacks) { // Constructing a dp matrix // of dimensions (S+1) x (N+1) int [,]dp = new int[S + 1, N + 1]; // Loop over all i stacks for(int i = 0; i < S; i++) { for(int j = 0; j <= N; j++) { for(int k = 0; k <= Math.Min(j, M); k++) { // Store the maximum of popping // j elements up to the current // stack by popping k elements // from current stack and // j - k elements from all // previous stacks combined dp[i + 1, j] = Math.Max(dp[i + 1, j], stacks[i, k] + dp[i, j - k]); } } } // Store the maximum sum of // popping N elements across // all stacks int result = int.MinValue; for(int i = 0; i <= N; i++) { result = Math.Max(result, dp[S, i]); } // dp[S,N] has the maximum sum return result; } // Driver code public static void Main(String[] args) { // Number of stacks int S = 2; // Length of each stack int M = 4; int [,]stacks = { { 2, 6, 4, 5 }, { 1, 6, 15, 10 } }; // Maximum elements that // can be popped int N = 3; Console.Write(maximumSum(S, M, N, stacks)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // Javascript Program to maximize the // sum of top of the stack // values of S stacks by popping // at most N elements // Function for computing the // maximum sum at the top of // the stacks after popping at // most N elements from S stack function maximumSum(S, M, N, stacks) { // Constructing a dp matrix // of dimensions (S+1) x (N+1) var dp = Array.from(Array(S+1), ()=> Array(N+1).fill(0)); // Loop over all i stacks for (var i = 0; i < S; i++) { for (var j = 0; j <= N; j++) { for (var k = 0; k <= Math.min(j, M); k++) { // Store the maximum of // popping j elements // up to the current stack // by popping k elements // from current stack and // j - k elements from all // previous stacks combined dp[i + 1][j] = Math.max(dp[i + 1][j], stacks[i][k] + dp[i][j - k]); } } } // Store the maximum sum of // popping N elements across // all stacks var result = -1000000000; for (var i = 0; i <= N; i++) { result = Math.max(result, dp[S][i]); } // dp[S][N] has the maximum sum return result; } // Driver Program // Number of stacks var S = 2; // Length of each stack var M = 4; var stacks = [ [ 2, 6, 4, 5 ], [ 1, 6, 15, 10 ] ]; // Maximum elements that // can be popped var N = 3; document.write( maximumSum(S, M, N, stacks)); </script>
21
Complejidad del tiempo: O( S*(M + N * (min(N, M))