Maximum tip calculator - naive solution

Question

I am working through a Geekforgeeks practice question. I have come up with a naive recursive solution to the "maximum tip calculator" problem.

The problem definition is:

Restaurant recieves N orders. If Rahul takes the ith order, gain $A[i]. If Ankit takes this order, the tip would be $B[i] One order per person. Rahul takes max X orders. Ankit takes max Y orders. X + Y >= N. Find out the maximum possible amount of total tip money after processing all the orders.

Input:

The first line contains one integer, number of test cases. The second line contains three integers N, X, Y. The third line contains N integers. The ith integer represents Ai. The fourth line contains N integers. The ith integer represents Bi.

Output: Print a single integer representing the maximum tip money they would receive.

My Code and working sample:

def max_tip(N, A, B, X, Y, n= 0):

    if n == len(A) or N == 0:
        return 0

    if X == 0 and Y > 0: # rahul cannot take more orders
        return max(B[n] + max_tip(N - 1, A, B, X, Y - 1, n + 1), # ankit takes the order
                    max_tip(N, A, B, X, Y, n + 1))  # ankit does not take order
    elif Y == 0 and X > 0: # ankit cannot take more orders
        return max(A[n] + max_tip(N - 1, A, B, X - 1, Y, n + 1), # rahul takes the order
                    max_tip(N, A, B, X, Y, n + 1)) # rahul does not take order
    elif Y == 0 and X == 0: # neither can take orders
        return 0
    else:
        return max(A[n] + max_tip(N - 1, A, B, X - 1, Y, n + 1), # rahul takes the order
                B[n] + max_tip(N - 1, A, B, X, Y - 1, n + 1), #ankit takes the order
                max_tip(N, A, B, X, Y, n + 1)) # nobody takes the order

T = int(input())

for i in range(T):
    nxy = [int(n) for n in input().strip().split(" ")]
    N = nxy[0]
    X = nxy[1]
    Y = nxy[2]

    A = [int(n) for n in input().strip().split(" ")]
    B = [int(n) for n in input().strip().split(" ")]

    print(max_tip(N, A, B, X, Y))

I've annotated my recursive call decisions. Essentially I extended the naive solution for 0-1 knapsack in another dimension two waiters, either one takes, the other takes, or both do not take the order depending on the orders left constraint.

The solution checker is complaining for the following testcase:

Input:
7 3 3
8 7 15 19 16 16 18
1 7 15 11 12 31 9

Its Correct output is:
110

And Your Code's Output is:
106

This confuses me because the optimal solution seems to be what my code is getting (19 + 16 + 18) + (7 + 15 + 31). The immediate issue seems to be that X + Y < N. My thought is my code should work for the case where X + Y < N as well.

What's going on?

Answer 1

you are considering the case, where nobody takes the tip. But that case doesn't exist as X+Y >= n. This java code worked for me, have a look.

private static int getMaxTip(int x, int y, int n, int[] A, int[] B) {
     int[][] dp = new int[x + 1][y + 1];

     dp[0][0] = 0;
     for (int i = 1;i <= x;i++) {
         dp[i][0] = (i <= n) ? dp[i - 1][0] + A[i - 1] : dp[i - 1][0];
     }

     for (int i = 1;i <= y;i++) {
         dp[0][i] = (i <= n) ? dp[0][i - 1] + B[i - 1] : dp[0][i - 1];
     }

     for (int i = 1;i <= x;i++) {
         for (int j = 1;j <= y;j++) {
             if (i + j <= n) {
                 dp[i][j] = Math.max(dp[i - 1][j] + A[i + j - 1], dp[i][j - 1] + B[i + j - 1]);
             }
         }
     }

     int ans = Integer.MIN_VALUE;
     for (int i = 0;i <= x;i++) {
         for (int j = 0;j <= y;j++) {
             if (i + j == n) {
                 ans = Math.max(ans, dp[i][j]);
             }
         }
     }
     return ans;
 }