如何从暴力枚举组合中求解奶牛运输最少行程最优解？

Alright, let's break down how to solve this problem—finding the smallest number of trips needed to move all your cows without exceeding a given weight limit—using brute-force enumeration with your existing get_partitions function. Here's a practical, step-by-step approach:

Background #

Your get_partitions function generates every possible way to split your cows into groups (each group represents one trip). Our goal is to check all these partitions, filter out the ones where every trip's total weight stays under the limit, and pick the partition with the fewest trips.

Step-by-Step Implementation #

1. Prepare Cow Weight Data #

First, you'll need a dictionary mapping each cow's name to its weight. For example:

cow_weights = {
    "Bessie": 450,
    "Daisy": 500,
    "Gertie": 275,
    "Henrietta": 350,
    "Maggie": 300
}

2. Iterate Through Partitions and Validate #

We'll loop through every partition generated by get_partitions, check if each trip in the partition is within the weight limit, and track the partition with the smallest number of trips. Here's the code:

def find_min_trips(cow_weights, weight_limit):
    all_cows = list(cow_weights.keys())
    min_trip_count = float('inf')
    best_transport_plan = None

    # Loop through every possible grouping of cows
    for partition in get_partitions(all_cows):
        is_valid = True
        # Check each trip's total weight
        for trip in partition:
            total_weight = sum(cow_weights[cow] for cow in trip)
            if total_weight > weight_limit:
                is_valid = False
                break  # No need to check further if this trip is over the limit
        
        # Update the best plan if this partition is valid and better than current best
        if is_valid and len(partition) < min_trip_count:
            min_trip_count = len(partition)
            best_transport_plan = partition

    return min_trip_count, best_transport_plan

3. Run the Function to Get Results #

Call the function with your cow weights and weight limit to get the optimal solution. For example, with a 1000-pound limit:

weight_limit = 1000
trips, plan = find_min_trips(cow_weights, weight_limit)
print(f"Minimum trips needed: {trips}")
print(f"Optimal transport plan: {plan}")

Key Notes #

• Performance Caveat: Brute-force enumeration gets slow really fast as you add more cows. The number of possible partitions follows the Bell number, which grows exponentially. This approach works great for small herds (8 cows or fewer), but you'll need a more efficient algorithm (like backtracking with pruning) for larger groups.
• Validate get_partitions: Make sure your helper function generates valid partitions—every cow should be in exactly one group, and no group should be empty.
• Unit Consistency: Double-check that your cow weights and weight limit use the same unit (e.g., pounds or kilograms) to avoid calculation errors.

Example Output #

For the cow_weights example above and a 1000-pound limit, you might get:

Minimum trips needed: 2
Optimal transport plan: [['Bessie', 'Daisy'], ['Gertie', 'Henrietta', 'Maggie']]

(The first trip totals 950 pounds, the second totals 925 pounds—both well under the limit.)

内容的提问来源于stack exchange，提问作者Kingle