Find maximum combination sum with two separate target values as constraints-CodePudding

Given an array of numbers (can include duplicates) - which represents the hours it takes for a car to be manufactured. And two numbers, which represent the hours that two factories that work. Find the maximum number of unique cars that can be produced.

Test case 1: [6, 5, 5, 4, 3] and 8, 9 The maximum combination is 4. 5 and 3 to sum 8, and 5 and 4 to sum 9.

Test case 2: [5, 5, 6] and 8, 8 The maximum combination is 2. The factory that works 8 hours can at most complete one vehicle that takes 5 hours, while the factory that works 9 hours can at most complete the vehicle that takes 6 hours.

I believe this question I am asking is similar to the Combination Sum II problem on Leetcode. But I am unable to solve it. Any ideas?

CodePudding user response：

hours = [6, 5, 5, 4, 3]
com_a = 8
com_b = 9

def get_max(hours, com_a, com_b):
    if len(hours) == 0: return 0
    max_cars_produced = 0
    # the order of hours matters, so we check which order provides the highest number
    for i in range(len(hours)):
        h = hours[i]
        child_1 = 0
        child_2 = 0
        
        # the order by which the companies are filled also matters
        # case I: where first company is filled first
        if h <= com_a: child_1 = get_max(hours[i 1:], com_a - h, com_b)
        elif h <= com_b: child_1 = get_max(hours[i 1:], com_a, com_b -h)
            
        # case 2: where second company is filled first
        if h <= com_b: child_2 = get_max(hours[i 1:], com_a, com_b -h)
        elif h <= com_a: child_2 = get_max(hours[i 1:], com_a - h, com_b)
            
        
        if h <= com_a or  h <= com_b:
            # if this satisfy this condition, it means that at least one car has been manufactured
            num_cars = max(child_1, child_2)   1 
            if num_cars > max_cars_produced: max_cars_produced = num_cars

    return max_cars_produced   

get_max(hours, com_a, com_b)

It is solved by recursive function. Every time it tries to see if a car (from hours array) can be manufactured by a company. And if it could, then it check the remaining cars (hours) to see if any of them can be manufactured (child).