Maximize Valid Trains from Shared Equipment

A freight rail terminal needs to assemble trains from available equipment. You are given a fleet of locomotives and a set of railcars. Each train must be formed by selecting exactly one locomotive and a non-empty subset of railcars subject to the following operating rules:

1. Equipment Exclusivity: Each locomotive and railcar can be assigned to at most one train.
2. Tonnage Capacity: The sum of weights of all railcars assigned to a train cannot exceed the locomotive's pulling capacity.
3. Length Constraint: The sum of lengths of all railcars assigned to a train cannot exceed max_car_length.
4. Car Count Limit: Each train must contain at least min_cars and at most max_cars railcars.

Your goal is to optimize the assembly lexicographically:

1. Primary Objective: Maximize the number of valid trains assembled.
2. Secondary Objective: Among configurations achieving the maximum number of trains, maximize the total railcar length across all assembled trains.

Write a function optimize_train_assembly(locomotives, cars, max_car_length, min_cars, max_cars) that returns a tuple (max_trains, max_total_car_length).

Interface

def optimize_train_assembly(
    locomotives: list[int],
    cars: list[tuple[int, int]],
    max_car_length: int,
    min_cars: int,
    max_cars: int
) -> tuple[int, int]:
    """
    locomotives: capacities of each locomotive [cap_0, cap_1, ...]
    cars: list of (weight, length) tuples for each railcar
    max_car_length: maximum allowed total railcar length per train
    min_cars: minimum number of cars per train
    max_cars: maximum number of cars per train
    
    Returns: (max_trains, max_total_car_length)
    """
    pass

Constraints

• 1 <= len(locomotives) <= 6
• 1 <= len(cars) <= 14
• 1 <= locomotives[i] <= 10^7
• 1 <= weight_j, length_j <= 10^6 for each car
• 1 <= max_car_length <= 10^7
• 1 <= min_cars <= max_cars <= len(cars)

Examples

Example 1

locomotives = [100, 80]
cars = [(50, 40), (40, 30), (30, 25), (20, 20)]
max_car_length = 60
min_cars = 1
max_cars = 2

# Output: (2, 95)
# Explanation:
# Train 1 (Locomotive cap 100): Car 0 (wt 50, len 40) + Car 2 (wt 30, len 25)
#   Total weight = 80  60 (Invalid! Length exceeded)
# Better configuration:
# Train 1 (Locomotive cap 100): Car 0 (wt 50, len 40) + Car 3 (wt 20, len 20)
#   Weight = 70 <= 100, length = 60 <= 60 (Valid, length = 60)
# Train 2 (Locomotive cap 80): Car 2 (wt 30, len 25)
#   Weight = 30 <= 80, length = 25 <= 60 (Valid, length = 25)
# Total cars = 3, total length = 85.
# An even better assignment:
# Train 1 (Locomotive cap 80): Car 1 (wt 40, len 30) + Car 3 (wt 20, len 20)
#   Weight = 60 <= 80, length = 50  60 (invalid).
# If Train 1 takes Car 1 (30) + Car 2 (25) = len 55, wt 70 <= 80.
# Train 2 takes Car 0 (40) = len 40, wt 50 <= 100. Total length = 95.

Example 2

locomotives = [50]
cars = [(60, 20), (70, 30)]
max_car_length = 100
min_cars = 1
max_cars = 2

# Output: (0, 0)
# Explanation: No locomotive has sufficient capacity to pull even a single car.