Maximice la suma de los elementos superiores de S pilas haciendo estallar como máximo N elementos

Posted on by Rudeus Greyrat

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: 
 

  1. 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.
  2. Inicialice todos los índices dp[][] en 0.
  3. Iterar sobre cada pila desde i = 0 hasta S – 1
  4. Ahora, para cada i -ésima pila, calcule la suma máxima posible haciendo estallar j (1 a N) elementos.
  5. 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.
  6. 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] .
  7. 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>
Producción: 

21

 

Complejidad del tiempo: O( S*(M + N * (min(N, M))
 

Publicación traducida automáticamente

Artículo escrito por ApurvaRaj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *