Калькулятор максимальных чаевых

Опубликовано: 19 Сентября, 2022

Рахул и Анкит — единственные два официанта в Королевском ресторане. Сегодня в ресторан поступило N заказов. Количество чаевых может различаться при обработке разными официантами, если Рахул возьмет i -й заказ, он получит чаевые в Ai рупий, а если Анкит возьмет этот заказ, чаевые будут Bi рупий.
Чтобы максимизировать общую сумму чаевых, они решили распределить заказ между собой. Один заказ будет обрабатываться только одним человеком. Кроме того, из-за нехватки времени Рахул не может выполнять более X заказов, а Анкит не может выполнять более Y заказов. Гарантируется, что X + Y больше или равно N , что означает, что все заказы могут быть обработаны либо Рахулом, либо Анкитом. Узнайте максимально возможную сумму общих денег чаевых после обработки всех заказов.

Примеры:

Input: A[] = {1, 2, 3, 4, 5}, B[] = {5, 4, 3, 2, 1}, X = 3, Y = 3 
Output: 21 
1st, 2nd and 3rd orders are taken by waiter Y. 
4th and 5th orders are taken by waiter X.

Input: A[] = {2, 2, 2}, B[] = {3, 3, 3}, X = 3, Y = 3 
Output: 9 

Рекурсивное решение: мы можем двигаться рекурсивным способом, чтобы вычислить максимальную сумму, которую нужно взять таким образом.
чтобы общая сумма чаевых была максимальной. Решение будет содержать 4 случая:

  1. i == n: Когда это достигнуто, это означает, что все заказы приняты. Так что верните 0 и вернитесь назад.
  2. X ≤ 0: когда официант X не может принимать больше заказов.
  3. Y ≤ 0: когда официант Y не может принимать больше заказов.
  4. max(Orders(X), Orders(Y)): нам нужно вернуть максимум чаевых, когда заказы принимаются как X , так и Y .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O( 2n )

Подход на основе DP: оптимальная подструктура предыдущего подхода содержит повторения, которых можно было бы избежать, сохраняя ранее рассчитанные подсказки в массиве. Это уменьшит временную сложность до O(n).

Ниже приведена реализация вышеуказанного подхода:

C++




// 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;
}

Python3



# 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.
Временная сложность: O(N)
 Космическая сложность: O(N 2 )

            

                            

                    
                                    

                        

                
РЕКОМЕНДУЕМЫЕ СТАТЬИ