Search code examples
pythonarraysalgorithmcombinations

Find maximum combination sum with two separate target values as constraints


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?


Solution

  • 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).