Calculadora de propinas máximas – Part 2

Rahul y Ankit son los dos únicos camareros del Royal Restaurant. Hoy, el restaurante recibió N pedidos. La cantidad de propinas puede diferir cuando las manejan diferentes camareros y se dan como arrays A[] y B[] , de modo que si Rahul toma la i ^-ésima orden, recibirá una propina de A[i] rupias, y si Ankit toma esta orden, el La propina sería B[i] rupias.

Para maximizar el valor total de la propina, decidieron distribuir el pedido entre ellos. Un pedido será manejado por una sola persona . Además, debido a limitaciones de tiempo , Rahul no puede aceptar más de X pedidos y Ankit no puede aceptar más de Y pedidos. Se garantiza que X + Y es mayor o igual que N , lo que significa que todos los pedidos pueden ser manejados por Rahul o Ankit. La tarea es averiguar la cantidad máxima posible de dinero total de propinas después de procesar todos los pedidos.

Ejemplos:

Entrada: N = 5, X = 3, Y = 3, A[] = {1, 2, 3, 4, 5}, B[] = {5, 4, 3, 2, 1}
Salida: 21
Explicación:
Paso 1: 5 está incluido en la array de Ankit
Paso 2:  4 está incluido en la array de Ankit
Paso 3:  Como ambos tienen el mismo valor 3, elija cualquiera de ellos
Paso 4: 4 está incluido en la array de Rahul
Paso 4: 5 está incluido de la array de Rahul
Por lo tanto, la cantidad máxima posible de dinero total de propinas suma 21.

Entrada: N = 7, X = 3, Y = 4, A[] = {8, 7, 15, 19, 16, 16, 18}, B[] = {1, 7, 15, 11, 12, 31 , 9}
Salida: 110

Enfoque ingenuo: el enfoque más simple es atravesar las arrays dadas y comenzar a atravesar ambas arrays simultáneamente y elegir el elemento máximo entre ellos y reducir el recuento de X si el elemento se toma de X , de lo contrario, el recuento de Y. Si uno de los X o Y se convierte en 0 , atraviesa otra array distinta de cero y agrega su valor a la ganancia máxima. Como en cada paso, hay una elección que hacer, esto es similar al problema de la mochila 0-1 , en el que se toman decisiones sobre si incluir o excluir un elemento.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that finds the maximum tips
// from the given arrays as per the
// given conditions
int maximumTip(vector<int> &arr1,vector<int> & arr2,
               int n, int x, int y)
{
     
    // Base Condition
    if (n == 0)
        return 0;
         
    // If both have non-zero count then
    // return max element from both array
    if (x != 0 and y != 0)
        return max(
            arr1[n - 1] + maximumTip(arr1, arr2, n - 1,
                                                 x - 1, y),
            arr2[n - 1] + maximumTip(arr1, arr2, n - 1, x,
                                                 y - 1));
 
    // Traverse first array, as y
    // count has become 0
    if (y == 0)
        return arr1[n - 1] + maximumTip(arr1, arr2, n - 1,
                                                    x - 1, y);
                                                     
    // Traverse 2nd array, as x
    // count has become 0
    else
        return arr2[n - 1] + maximumTip(arr1, arr2, n - 1,
                                                 x, y - 1);
}
 
// Drive Code
int main()
{
    int N = 5;
    int X = 3;
    int Y = 3;
     
    vector<int> A = { 1, 2, 3, 4, 5 };
    vector<int> B = { 5, 4, 3, 2, 1 };
     
    // Function Call
    cout << (maximumTip(A, B, N, X, Y));
}
 
// This code is contributed by mohit kumar 29

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG
{
   
  // Function that finds the maximum tips
// from the given arrays as per the
// given conditions
static int maximumTip(int []arr1,int []arr2,
               int n, int x, int y)
{
     
    // Base Condition
    if (n == 0)
        return 0;
         
    // If both have non-zero count then
    // return max element from both array
    if (x != 0 && y != 0)
        return Math.max(
            arr1[n - 1] + maximumTip(arr1, arr2, n - 1,
                                                 x - 1, y),
            arr2[n - 1] + maximumTip(arr1, arr2, n - 1, x,
                                                 y - 1));
 
    // Traverse first array, as y
    // count has become 0
    if (y == 0)
        return arr1[n - 1] + maximumTip(arr1, arr2, n - 1,
                                                    x - 1, y);
                                                     
    // Traverse 2nd array, as x
    // count has become 0
    else
        return arr2[n - 1] + maximumTip(arr1, arr2, n - 1,
                                                 x, y - 1);
}
 
// Drive Code
    public static void main (String[] args) {
       int N = 5;
    int X = 3;
    int Y = 3;
     
    int A[] = { 1, 2, 3, 4, 5 };
    int B[] = { 5, 4, 3, 2, 1 };
     
    // Function Call
             
        System.out.println(maximumTip(A, B, N, X, Y));
    }
}
 
    // This code is contributed by Potta Lokesh

# Python program for the above approach
 
# Function that finds the maximum tips
# from the given arrays as per the
# given conditions
def maximumTip(arr1, arr2, n, x, y):
 
    # Base Condition
    if n == 0:
        return 0
 
    # If both have non-zero count then
    # return max element from both array
    if x != 0 and y != 0:
        return max(
            arr1[n-1] + maximumTip(arr1, arr2, n - 1, x-1, y),
            arr2[n-1] + maximumTip(arr1, arr2, n-1, x, y-1)
            )
 
    # Traverse first array, as y
    # count has become 0
    if y == 0:
        return arr1[n-1] + maximumTip(arr1, arr2, n-1, x-1, y)
 
    # Traverse 2nd array, as x
    # count has become 0
    else:
        return arr2[n - 1] + maximumTip(arr1, arr2, n-1, x, y-1)
 
 
# Drive Code
N = 5
X = 3
Y = 3
A = [1, 2, 3, 4, 5]
B = [5, 4, 3, 2, 1]
 
# Function Call
print(maximumTip(A, B, N, X, Y))

/*package whatever //do not write package name here */
using System;
public class GFG
{
 
  // Function that finds the maximum tips
  // from the given arrays as per the
  // given conditions
  static int maximumTip(int []arr1,int []arr2,
                        int n, int x, int y)
  {
 
    // Base Condition
    if (n == 0)
      return 0;
 
    // If both have non-zero count then
    // return max element from both array
    if (x != 0 && y != 0)
      return Math.Max(
      arr1[n - 1] + maximumTip(arr1, arr2, n - 1,
                               x - 1, y),
      arr2[n - 1] + maximumTip(arr1, arr2, n - 1, x,
                               y - 1));
 
    // Traverse first array, as y
    // count has become 0
    if (y == 0)
      return arr1[n - 1] + maximumTip(arr1, arr2, n - 1,
                                      x - 1, y);
 
    // Traverse 2nd array, as x
    // count has become 0
    else
      return arr2[n - 1] + maximumTip(arr1, arr2, n - 1,
                                      x, y - 1);
  }
 
  // Drive Code
  public static void Main(String[] args) {
    int N = 5;
    int X = 3;
    int Y = 3;
 
    int []A = { 1, 2, 3, 4, 5 };
    int []B = { 5, 4, 3, 2, 1 };
 
    // Function Call
    Console.WriteLine(maximumTip(A, B, N, X, Y));
  }
}
 
// This code is contributed by umadevi9616

<script>
        // JavaScript Program for the above approach
 
        // Function that finds the maximum tips
        // from the given arrays as per the
        // given conditions
        function maximumTip(arr1, arr2, n, x, y) {
 
            // Base Condition
            if (n == 0)
                return 0;
 
            // If both have non-zero count then
            // return max element from both array
            if (x != 0 && y != 0)
                return Math.max(
                    arr1[n - 1] + maximumTip(arr1, arr2, n - 1,
                        x - 1, y),
                    arr2[n - 1] + maximumTip(arr1, arr2, n - 1, x,
                        y - 1));
 
            // Traverse first array, as y
            // count has become 0
            if (y == 0)
                return arr1[n - 1] + maximumTip(arr1, arr2, n - 1,
                    x - 1, y);
 
            // Traverse 2nd array, as x
            // count has become 0
            else
                return arr2[n - 1] + maximumTip(arr1, arr2, n - 1,
                    x, y - 1);
        }
 
        // Drive Code
 
        let N = 5;
        let X = 3;
        let Y = 3;
 
        let A = [1, 2, 3, 4, 5];
        let B = [5, 4, 3, 2, 1];
 
        // Function Call
        document.write(maximumTip(A, B, N, X, Y));
 
 
    // This code is contributed by Potta Lokesh
 
    </script>

21

Complejidad temporal: O(2 ^N )
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de programación dinámica y memorización . Si se rastrea la ejecución para los valores de N , X , Y , se puede ver que hay subproblemas superpuestos . Estos subproblemas superpuestos se pueden calcular una vez y almacenar y utilizar cuando se llama al mismo subproblema en la llamada recursiva . A continuación se muestran los pasos:

• Inicialice un Mapa/Diccionario para almacenar el resultado de los subproblemas superpuestos. Las claves del mapa serán valores combinados de N , X e Y .
• En cada llamada recursiva, verifique si una clave determinada está presente en el mapa y luego devuelva el valor del mapa mismo.
• De lo contrario, llame a la función de forma recursiva y almacene el valor en el mapa y devuelva el valor almacenado.
• Si X e Y son distintos de cero, llame recursivamente a la función y tome el máximo del valor devuelto cuando se usa X y cuando se usa Y.
• Si X o Y es cero, llame recursivamente a la array distinta de cero.
• Después de que finalicen las llamadas recursivas anteriores, imprima la cantidad máxima posible de propina calculada.

A continuación se muestra la implementación del enfoque anterior:

#include <bits/stdc++.h>
using namespace std;
int dp[1001][101][101];
int rec(int level, int x, int y, int arr1[], int arr2[],
        int n)
{
    if (level == n)
        return 0;
    if (x == 0 && y == 0)
        return 0;
    if (x == 0)
        return arr2[level]
               + rec(level + 1, x, y - 1, arr1, arr2, n);
    if (y == 0)
        return arr1[level]
               + rec(level + 1, x - 1, y, arr1, arr2, n);
    if (dp[level][x][y] != -1)
        return dp[level][x][y];
    int ans = max(rec(level + 1, x - 1, y, arr1, arr2, n)
                      + arr1[level],
                  rec(level + 1, x, y - 1, arr1, arr2, n)
                      + arr2[level]);
    return dp[level][x][y] = ans;
}
 
void solve()
{
    int n = 7, x = 3, y = 4;
    int arr1[] = { 8, 7, 15, 19, 16, 16, 18 },
        arr2[] = { 1, 7, 15, 11, 12, 31, 9 };
    memset(dp, -1, sizeof(dp));
    cout << rec(0, x, y, arr1, arr2, n);
}
int main()
{
    solve();
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.HashMap;
 
class GFG {
 
    // Function that finds the maximum tips
    // from the given arrays as per the
    // given conditions
    static int maximumTip(int[] arr1, int[] arr2, int n,
                          int x, int y,
                          HashMap<String, Integer> dd)
    {
        // Create key of N, X, Y
        String key = Integer.toString(n) + "_"
                     + Integer.toString(x) + "_"
                     + Integer.toString(y);
       
        // Return if the current state is
        // already calculated
        if (dd.get(key) != null)
            return dd.get(key);
        // Base Condition
        if (n == 0)
            return 0;
 
        // If both have non-zero count then store and
        // return max element from both array
        if (x != 0 && y != 0) {
            int temp = Math.max(
                arr1[n - 1]
                    + maximumTip(arr1, arr2, n - 1, x - 1,
                                 y, dd),
                arr2[n - 1]
                    + maximumTip(arr1, arr2, n - 1, x,
                                 y - 1, dd));
            dd.put(key, temp);
            // Return the current state result
            return dd.get(key);
        }
 
        // if y is zero, only x value
        // can be used
        if (y == 0) {
            int temp = arr1[n - 1]
                       + maximumTip(arr1, arr2, n - 1,
                                    x - 1, y, dd);
            dd.put(key, temp);
            // Return the current state result
            return dd.get(key);
        }
 
        // if x is zero, only y value
        // can be used
        else {
            int temp = arr2[n - 1]
                       + maximumTip(arr1, arr2, n - 1, x,
                                    y - 1, dd);
            dd.put(key, temp);
            // Return the current state result
            return dd.get(key);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 5;
        int X = 3;
        int Y = 3;
 
        int A[] = { 1, 2, 3, 4, 5 };
        int B[] = { 5, 4, 3, 2, 1 };
       
        // Stores the results of the
        // overlapping state
        HashMap<String, Integer> dd
            = new HashMap<String, Integer>();
       
        // Function Call
        System.out.println(maximumTip(A, B, N, X, Y, dd));
    }
}
 
// This code is contributed by MuskanKalra1

# Python program for the above approach
 
 
# Function that finds the maximum tips
# from the given arrays as per the
# given conditions
def maximumTip(arr1, arr2, n, x, y, dd):
 
    # Create key of N, X, Y
    key = str(n) + '_' + str(x) + '_' + str(y)
 
    # Return if the current state is
    # already calculated
    if key in dd:
        return dd[key]
 
    # Base Condition
    if n == 0:
        return 0
 
    # Store and return
    if x != 0 and y != 0:
        dd[key] = max(
            arr1[n-1] + maximumTip(arr1, arr2, n-1, x-1, y, dd),
            arr2[n-1] + maximumTip(arr1, arr2, n-1, x, y-1, dd)
        )
 
        # Return the current state result
        return dd[key]
 
    # If y is zero, only x value
    # can be used
    if y == 0:
        dd[key] = arr1[n-1] + maximumTip(arr1, arr2, n-1, x-1, y, dd)
 
        # Return the current state result
        return dd[key]
 
    # If x is zero, only y value
    # can be used
    else:
 
        dd[key] = arr2[n-1] + maximumTip(arr1, arr2, n-1, x, y-1, dd)
 
        # Return the current state result
        return dd[key]
 
 
# Drive Code
N = 5
X = 3
Y = 3
A = [1, 2, 3, 4, 5]
B = [5, 4, 3, 2, 1]
 
# Stores the results of the
# overlapping state
dd = {}
 
# Function Call
print(maximumTip(A, B, N, X, Y, dd))

<script>
 
// JavaScript program for the above approach
// Function that finds the maximum tips
// from the given arrays as per the
// given conditions
 
function maximumTip(arr1, arr2, n, x, y, dd) {
  // Create key of N, X, Y
  key = `${n}_${x}_${y}`;
   
  // Return if the current state is
  // already calculated
  for (var key in dd) {
    return dd[key];
  }
 
  // Base Condition
  if (n == 0) {
    return 0;
  }
 
  // Store and return
  if (x != 0 && y != 0) {
    dd[key] = Math.max(
      arr1[n - 1] + maximumTip(arr1, arr2, n - 1, x - 1, y, dd),
      arr2[n - 1] + maximumTip(arr1, arr2, n - 1, x, y - 1, dd)
    );
 
    // Return the current state result
    return dd[key];
  }
 
  // If y is zero, only x value
  // can be used
  if (y == 0)
  {
    dd[key] = arr1[n - 1] + maximumTip(arr1, arr2, n - 1, x - 1, y, dd);
     
    // Return the current state result
    return dd[key];
  }
  // If x is zero, only y value
  // can be used
  else {
    dd[key] = arr2[n - 1] + maximumTip(arr1, arr2, n - 1, x, y - 1, dd);
    // Return the current state result
    return dd[key];
  }
}
 
// Drive Code
let N = 5;
let X = 3;
let Y = 3;
let A = [1, 2, 3, 4, 5];
let B = [5, 4, 3, 2, 1];
 
// Stores the results of the
// overlapping state
dd = {};
 
// Function Call
document.write(maximumTip(A, B, N, X, Y, dd));
 
// This code is contributed by rdtank.
</script>

21

Complejidad de Tiempo: O(N*X*Y)
Espacio Auxiliar: O(N*X*Y)