a,b represent tips for worker a and b for each order.
n is the number of orders
x is the number of orders worker a can handle
y is the number of orders worker b can handle

This is the code I'm using:

def maxTip(self, a, b, n, x, y):
    idx=[[],[],[]]
    for i in range(len(a)):
        if a[i]>b[i]:
            idx[0].append(i)
        elif b[i]>a[i]:
            idx[1].append(i)
        else:
            idx[2].append(i)
    def findSum(arr):
        sum1=0
        sum2=0
    
        for index in idx[0]:
            sum1 =a[index]
            
        for index in idx[1]:
            sum2 =b[index]
        return sum1 sum2
    
    i=0
    while len(idx[0])<x:
        idx[0].append(idx[2][i])
        i =1
    while len(idx[1])<y and i<len(idx[2]):
        idx[1].append(idx[2][i])
        i =1
    return(findSum(idx))

I am searching through ith index of both lists at the same time to find the relative maximum at that index. If the ith element of a is greater than the ith element of b then that element gets appended to the first subarray of the array defined at the beginning. Similarly, it is done for the larger element of b. The remaining or the equal values are appended to the third sublist. When I need to find the maximum tip, I go through a loop till x to add the elements of the third subarray to the first subarray. When the length is x, I add the rest of the elements to the next subarray. Then I find the sum. It works with some inputs. But it fails most of the time.

I have recently started learning algorithms so this might be a very stupid question for many.

Example:

n=5 
x=3 
y=3 
a=[1,2,3,4,5] 
b=[5,4,3,2,1]

Here the maximum sum would be 21. Worker a will take orders 3,4,5 and worker b will take order 1,2. Worker a will get (3 4 5)=12 amount and worker b will get (5 4)=9 and 12 9=21.

What should I do to find the correct output for:

n=7
x=3
y=4
a=[8, 7, 5, 9, 6, 6, 8]
b=[1, 7, 5, 1, 2, 3, 9]

CodePudding user response：

Problem Description

Given two arrays of size N and two integers X and Y indicating the maximum number of elements, one can pick from array A and array B respectively. At each ith turn, either A[i] or B[i] can be picked. The task is to make the selection that results in the maximum possible sum. Note: It is guaranteed that (X Y) ≥ N.

Posted Code

Provides incorrect answers for a simple solution such as:

x, y = 1, 1
a = [10, 100]
b = [1, 1]
n = 2
print(Solution().maxTip(a, b, n, x, y))
# Outputs: 110 

Error: the correct answer is 101 (not 110)

Better Solution

Translating to Python the approach from Maximum sum by picking elements from two arrays in order which are in C , and JavaScript

Steps:

1. Sort the element pairs according to the absolute difference i.e. |A[i] – B[i]| in decreasing order.
2. Compare A[i] and B[i] value, the one which is greater adds that value to the sum.
3. Decrement X by one if the element is chosen from A[i] else decrement Y by one.
4. If x is out or y is out add min(A[i], B[i]) to sum

Code

class Solution:
    def maxTip(self, a, b, n, x, y):
        """
        : a   - can pick either from array a
        : b     or array b on each turn
        : n   - length of a & b
        : x   - number of times can pick from a
        : y   - number of times can pick from b
        """
        # Step 1: Sort the element pairs according to the absolute differenc
        ab_pairs = sorted([p for p in zip(a, b)],               # sequence of a, b pairs formed by zip(a, b)
                          key = lambda kv: abs(kv[0] - kv[1]),  # sorting pairs based upon absolute difference
                          reverse = True)                       # sort in non-ascending order
        tsum = 0
        for ai, bi in ab_pairs:
            if ai > bi and x > 0:    # 2. Compare A[i] and B[i] value,
                tsum  = ai           #    the one which is greater adds that value to the sum.
                x -= 1               # 3. Decrement X by one if the element is chosen from A[i]
            elif bi > ai and y > 0:  # 2. Compare A[i] and B[i] value,
                tsum  = bi           #    the one which is greater adds that value to the sum.
                y -= 1               # 3. else decrement Y by one.
            else:
                tsum  = min(ai, bi)  # 4. If x is out or y is out add min(A[i], B[i]) to sum

        return tsum

Test

n=7
x=3
y=4
a=[8, 7, 5, 9, 6, 6, 8]
b=[1, 7, 5, 1, 2, 3, 9]
print(Solution().maxTip(a, b, n, x, y)
# Output: 47