Calculadora de propinas máximas – Part 1

Rahul y Ankit son los únicos dos camareros en Royal Restaurant. Hoy, el restaurante recibió N pedidos. La cantidad de propinas puede diferir cuando los manejan diferentes meseros, si Rahul toma la i-ésima orden, se le daría una propina de Ai rupias y si Ankit toma esta orden, la propina sería de Bi 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. Averigüe la cantidad máxima posible de dinero total de propinas después de procesar todos los pedidos.

Ejemplos: 

Entrada: A[] = {1, 2, 3, 4, 5}, B[] = {5, 4, 3, 2, 1}, X = 3, Y = 3 
Salida: 21 
órdenes 1, 2 y 3 son tomados por el mesero Y. 
Los pedidos 4 y 5 son tomados por el mesero X.

Entrada: A[] = {2, 2, 2}, B[] = {3, 3, 3}, X = 3, Y = 3 
Salida: 9 

Solución recursiva: Podemos movernos de forma recursiva para calcular la cantidad máxima de pedido a tomar de tal manera 
que la propina total sea máxima. La solución contendría 4 casos:  

1. i == n: Cuando se alcanza esto significa que se tomaron todas las órdenes. Así que devuelve 0 y retrocede.
2. X ≤ 0: Cuando el camarero X no puede tomar más pedidos.
3. Y ≤ 0: Cuando el mesero Y no puede tomar más pedidos.
4. max(Pedidos(X), Pedidos(Y)): Necesitamos devolver el máximo de propina cuando los pedidos son tomados por X e Y .

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

// C++ implementation of the approach
 
#include <bits/stdc++.h>
using namespace std;
int n;
 
// Recursive function to calculate sum of
// maximum tip order taken by X and Y
int solve(int i, int X, int Y,
          int a[], int b[], int n)
{
 
    // When all orders have been taken
    if (i == n)
        return 0;
 
    // When X cannot take more orders
    if (X <= 0)
        return b[i] + solve(i + 1, X,
                            Y - 1, a, b, n);
 
    // When Y cannot take more orders
    if (Y <= 0)
        return a[i] + solve(i + 1, X - 1,
                            Y, a, b, n);
 
    // When both can take order
    // calculate maximum out of two
    else
        return max(a[i] + solve(i + 1, X - 1,
                                Y, a, b, n),
                   b[i] + solve(i + 1, X,
                                Y - 1, a, b, n));
}
 
// Driver code
int main()
{
    int a[] = { 1, 2, 3, 4, 5 };
    int b[] = { 5, 4, 3, 2, 1 };
    int n = sizeof(a) / sizeof(a[0]);
    int x = 3, y = 3;
 
    cout << solve(0, x, y, a, b, n);
 
    return 0;
}

// Java implementation for the above approach
import java.io.*;
 
class GFG
{
    static int n;
 
    // Recursive function to calculate sum of
    // maximum tip order taken by X and Y
    static int solve(int i, int X, int Y, int a[], int b[],
                     int n)
    {
 
        // When all orders have been taken
        if (i == n)
            return 0;
 
        // When X cannot take more orders
        if (X <= 0)
            return b[i] + solve(i + 1, X, Y - 1, a, b, n);
 
        // When Y cannot take more orders
        if (Y <= 0)
            return a[i] + solve(i + 1, X - 1, Y, a, b, n);
 
        // When both can take order
        // calculate maximum out of two
        else
            return Math.max(
                a[i] + solve(i + 1, X - 1, Y, a, b, n),
                b[i] + solve(i + 1, X, Y - 1, a, b, n));
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int a[] = { 1, 2, 3, 4, 5 };
        int b[] = { 5, 4, 3, 2, 1 };
        int n = a.length;
        int x = 3, y = 3;
 
        System.out.println(solve(0, x, y, a, b, n));
    }
}
 
// This code is contributed by Potta Lokesh

# Python3 program for the above approach
 
# Recursive function to calculate sum of
# maximum tip order taken by X and Y
def solve(i, X, Y,
          a, b, n) :
 
    # When all orders have been taken
    if (i == n):
        return 0
 
    # When X cannot take more orders
    if (X <= 0):
        return (b[i] + solve(i + 1, X,
                            Y - 1, a, b, n))
 
    # When Y cannot take more orders
    if (Y <= 0):
        return (a[i] + solve(i + 1, X - 1,
                            Y, a, b, n))
 
    # When both can take order
    # calculate maximum out of two
    else:
        return max(a[i] + solve(i + 1, X - 1,
                                Y, a, b, n),
                   b[i] + solve(i + 1, X,
                                Y - 1, a, b, n))
 
# Driver code
a = [ 1, 2, 3, 4, 5 ]
b = [ 5, 4, 3, 2, 1 ]
 
n = len(a)
 
x = 3
y = 3
 
print(solve(0, x, y, a, b, n))
 
# This code is contributed by splevel62.

// C# program for the above approach
using System;
 
class GFG{
 
static int n;
 
// Recursive function to calculate sum of
// maximum tip order taken by X and Y
static int solve(int i, int X, int Y,
                 int[] a, int[] b, int n)
{
     
    // When all orders have been taken
    if (i == n)
        return 0;
 
    // When X cannot take more orders
    if (X <= 0)
        return b[i] + solve(i + 1, X, Y - 1,
                            a, b, n);
 
    // When Y cannot take more orders
    if (Y <= 0)
        return a[i] + solve(i + 1, X - 1, Y,
                            a, b, n);
 
    // When both can take order
    // calculate maximum out of two
    else
        return Math.Max(
            a[i] + solve(i + 1, X - 1, Y, a, b, n),
            b[i] + solve(i + 1, X, Y - 1, a, b, n));
}
 
// Driver Code
public static void Main(String[] args)
{
    int[] a = { 1, 2, 3, 4, 5 };
    int[] b = { 5, 4, 3, 2, 1 };
    // int n = a.Length;
    int x = 3, y = 3;
 
    Console.Write(solve(0, x, y, a, b, n));
}
}
 
// This code is contributed by sanjoy_62

<script>
 
// JavaScript implementation of the approach
 
let n;
 
// Recursive function to calculate sum of
// maximum tip order taken by X and Y
function solve(i, X, Y, a, b, n) {
  // When all orders have been taken
  if (i == n) return 0;
 
  // When X cannot take more orders
  if (X <= 0) return b[i] + solve(i + 1, X, Y - 1, a, b, n);
 
  // When Y cannot take more orders
  if (Y <= 0) return a[i] + solve(i + 1, X - 1, Y, a, b, n);
  // When both can take order
  // calculate maximum out of two
  else
    return Math.max(
      a[i] + solve(i + 1, X - 1, Y, a, b, n),
      b[i] + solve(i + 1, X, Y - 1, a, b, n)
    );
}
 
// Driver code
 
let a = [1, 2, 3, 4, 5];
let b = [5, 4, 3, 2, 1];
n = a.length;
let x = 3,
  y = 3;
 
document.write(solve(0, x, y, a, b, n));
 
</script>

21

Complejidad del tiempo: O(2 ⁿ )

Enfoque basado en DP: la subestructura óptima del enfoque anterior contiene repeticiones que podrían evitarse almacenando consejos previamente calculados en la array. Esto reduciría la complejidad del tiempo a O(n).

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Global Variables
int N, X, Y;
 
vector<int> A_right_sum, B_right_sum;
vector<unordered_map<int,
                     unordered_map<int, int> > >
    mem;
vector<unordered_map<int,
                     unordered_map<int, bool> > >
    vis;
 
// Function to check if visited before
bool get_vis_val(int i, int x, int y)
{
    if (i == N)
        return true;
    return vis[i][x][y];
}
 
// Function to return the tip value
int get_mem_val(int i, int x, int y)
{
    if (i == N)
        return 0;
    return mem[i][x][y];
}
 
// Function to calculate the maximum tip possible
void find_ans(int i, int x, int y,
              vector<int> A, vector<int> B)
{
 
    // If already visited
    if (get_vis_val(i, x, y))
        return;
 
    vis[i][x][y] = true;
 
    // If X cannot take more orders
    if (x == 0) {
        mem[i][x][y] = B_right_sum[i];
    }
 
    // If Y cannot take more orders
    else if (y == 0) {
        mem[i][x][y] = A_right_sum[i];
    }
 
    // If both can take orders then
    // calculate the maximum of two
    else {
        find_ans(i + 1, x - 1, y, A, B);
        find_ans(i + 1, x, y - 1, A, B);
        mem[i][x][y]
            = max(get_mem_val(i + 1, x - 1, y)
                      + A[i],
                  get_mem_val(i + 1, x, y - 1)
                      + B[i]);
    }
}
 
// Driver code
int main()
{
 
    int a[] = { 1, 2, 3, 4, 5 };
    int b[] = { 5, 4, 3, 2, 1 };
    N = sizeof(a) / sizeof(a[0]);
    X = 3;
    Y = 3;
 
    // Vector containing the tips of waiter X
    vector<int> A(a, a + N);
 
    // Vector containing the tips of waiter Y
    vector<int> B(b, b + N);
 
    // Memory allocation and clearing
    // of previous caches
    mem.clear();
    mem.resize(N + 1);
    vis.clear();
    vis.resize(N + 1);
 
    A_right_sum.resize(N);
    B_right_sum.resize(N);
 
    A_right_sum[N - 1] = A[N - 1];
    B_right_sum[N - 1] = B[N - 1];
 
    // Precalculation of sums
    // of tip at each ith order
    for (int i = N - 2; i >= 0; i--) {
        A_right_sum[i]
            = A_right_sum[i + 1] + A[i];
        B_right_sum[i]
            = B_right_sum[i + 1] + B[i];
    }
 
    // Bottom up dp based solution
    find_ans(0, X, Y, A, B);
 
    // Final ans stored in mem[0][X][Y]
    cout << get_mem_val(0, X, Y) << endl;
 
    return 0;
}

# Python program for the above approach:
 
## Global Variables
N = 0
X = 0
Y = 0
 
A_right_sum = []
B_right_sum = []
# vector<unordered_map<int, unordered_map<int, int> > > mem;
# vector<unordered_map<int, unordered_map<int, bool> > > vis;
mem = []
vis = []
 
## Function to check if visited before
def get_vis_val(i, x, y):
    if (i == N):
        return True
    if(x not in vis[i]):
        return False
    if(y not in vis[i][x]):
        return False
    return vis[i][x][y]
 
## Function to return the tip value
def get_mem_val(i, x, y):
    if (i == N):
        return 0
    if(x not in mem[i]):
        return 0
    if(y not in mem[i][x]):
        return 0
    return mem[i][x][y]
 
## Function to calculate the maximum tip possible
def find_ans(i, x, y, A, B):
 
    ## If already visited
    if (get_vis_val(i, x, y)):
        return;
 
    if(x not in vis[i]):
        vis[i][x] = {}
    vis[i][x][y] = True
 
    ## If X cannot take more orders
    if (x == 0):
        if(x not in mem[i]):
            mem[i][x] = {}
        mem[i][x][y] = B_right_sum[i]
 
    ## If Y cannot take more orders
    elif (y == 0):
        if(x not in mem[i]):
            mem[i][x] = {}
        mem[i][x][y] = A_right_sum[i]
 
    ## If both can take orders then
    ## calculate the maximum of two
    else:
        find_ans(i + 1, x - 1, y, A, B)
        find_ans(i + 1, x, y - 1, A, B)
        if(x not in mem[i]):
            mem[i][x] = {}
        mem[i][x][y] = max(get_mem_val(i + 1, x - 1, y) + A[i], get_mem_val(i + 1, x, y - 1) + B[i])
 
## Driver code
if __name__=='__main__':
 
    a = [ 1, 2, 3, 4, 5 ]
    b = [ 5, 4, 3, 2, 1 ]
    N = len(a)
    X = 3
    Y = 3
 
    ## Vector containing the tips of waiter X
    A = []
    for i in range(0, N):
        A.append(a[i])
 
    ## Vector containing the tips of waiter Y
    B = []
    for i in range(0, N):
        B.append(b[i])
 
    ## Memory allocation and clearing
    ## of previous caches
    mem.clear();
    for i in range(0, N+1):
        mem.append({})
 
    vis.clear();
    for i in range(0, N+1):
        vis.append({})
 
    for i in range(0, N):
        A_right_sum.append(0);
        B_right_sum.append(0);
 
    A_right_sum[N - 1] = A[N - 1];
    B_right_sum[N - 1] = B[N - 1];
 
    ## Precalculation of sums
    ## of tip at each ith order
    for i in range(N-2, -1, -1):
        A_right_sum[i] = A_right_sum[i + 1] + A[i]
        B_right_sum[i] = B_right_sum[i + 1] + B[i]
 
    ## Bottom up dp based solution
    find_ans(0, X, Y, A, B);
 
    ## Final ans stored in mem[0][X][Y]
    print(get_mem_val(0, X, Y))
 
    # This code is contributed by subhamgoyal2014.

21

Complejidad Temporal: O(N) 
Complejidad Espacial: O(N ² )