基于MySQL数据库的多物品比例组合优化计算方案咨询

Great question! Let's walk through how to efficiently solve this combination matching problem with your MySQL dataset—since you're dealing with 150+ items and need precise matches using 1x, 0.5x, or 0.25x multipliers, we need a balanced approach between database optimization and smart algorithm design.

Key Problem Breakdown #

First, let's clarify the core requirement: we need to select a subset of items (each can be used once with one of three multipliers: 1, 1/2, 1/4) such that the sum of their scaled A/B/C values exactly matches the target TA/TB/TC. The challenge is avoiding brute-force combinations (which would be computationally infeasible for 150 items) while ensuring accuracy.

Critical Preprocessing Step: Expand Multiplier Options #

Since each item has 3 valid multiplier choices, we can first expand our dataset to include these options explicitly. This transforms the problem into selecting non-overlapping items (by original ItemID) from this expanded set whose sum hits the target.

Why This Helps: #

• Simplifies the matching logic by treating each multiplier variant as a distinct candidate (but we'll enforce that only one variant per original item is used).
• Allows us to pre-filter invalid candidates (e.g., any variant where scaled A > TA is discarded upfront).

Option 1: MySQL Recursive CTE (For Database-Only Implementation) #

If you prefer to handle everything in MySQL (8.0+ required for recursive CTEs), here's an optimized approach:

Step 1: Define Expanded Candidates with Pre-Filtering #

First, create a CTE that generates all valid multiplier variants for each item (we'll use integer scaling to avoid floating-point precision errors):

SET @target_A = 60; -- Replace with user's target A
SET @target_B = 43; -- Replace with user's target B
SET @target_C = 34; -- Replace with user's target C
SET @scale = 4; -- Convert all values to integers to avoid float errors

WITH expanded_items AS (
    -- 1x multiplier (scaled by 4)
    SELECT 
        ItemID,
        A * @scale AS A_val,
        B * @scale AS B_val,
        C * @scale AS C_val,
        '1x' AS multiplier
    FROM items
    WHERE A <= @target_A AND B <= @target_B AND C <= @target_C

    UNION ALL

    -- 0.5x multiplier (scaled to 2x original)
    SELECT 
        ItemID,
        A * 2 AS A_val,
        B * 2 AS B_val,
        C * 2 AS C_val,
        '0.5x' AS multiplier
    FROM items
    WHERE (A * 0.5) <= @target_A AND (B * 0.5) <= @target_B AND (C * 0.5) <= @target_C

    UNION ALL

    -- 0.25x multiplier (scaled to 1x original)
    SELECT 
        ItemID,
        A * 1 AS A_val,
        B * 1 AS B_val,
        C * 1 AS C_val,
        '0.25x' AS multiplier
    FROM items
    WHERE (A * 0.25) <= @target_A AND (B * 0.25) <= @target_B AND (C * 0.25) <= @target_C
),

Step 2: Recursive Combination Building #

Next, use a recursive CTE to build valid combinations, ensuring no duplicate original items are used and stopping when we hit the scaled target sum:

recursive_combinations AS (
    -- Base case: single-item matches
    SELECT 
        CONCAT(ItemID, '(', multiplier, ')') AS combination,
        A_val AS total_A,
        B_val AS total_B,
        C_val AS total_C,
        JSON_ARRAY(ItemID) AS used_item_ids,
        1 AS depth
    FROM expanded_items
    WHERE A_val = @target_A * @scale 
      AND B_val = @target_B * @scale 
      AND C_val = @target_C * @scale

    UNION ALL

    -- Recursive step: add new items to existing combinations
    SELECT 
        CONCAT(rc.combination, ', ', ei.ItemID, '(', ei.multiplier, ')') AS combination,
        rc.total_A + ei.A_val AS total_A,
        rc.total_B + ei.B_val AS total_B,
        rc.total_C + ei.C_val AS total_C,
        JSON_ARRAY_APPEND(rc.used_item_ids, '$', ei.ItemID) AS used_item_ids,
        rc.depth + 1 AS depth
    FROM recursive_combinations rc
    JOIN expanded_items ei 
        ON NOT JSON_CONTAINS(rc.used_item_ids, CONCAT('"', ei.ItemID, '"')) -- Prevent duplicate items
        AND rc.total_A + ei.A_val <= @target_A * @scale
        AND rc.total_B + ei.B_val <= @target_B * @scale
        AND rc.total_C + ei.C_val <= @target_C * @scale
        AND rc.depth <= 4 -- Limit depth (max 4 items with 0.25x to reach 1x equivalent)
    HAVING total_A = @target_A * @scale 
       AND total_B = @target_B * @scale 
       AND total_C = @target_C * @scale
)
-- Final results: all valid combinations
SELECT combination FROM recursive_combinations;

Performance Tips for MySQL Approach: #

• Add Indexes: Create indexes on items(A), items(B), items(C) to speed up pre-filtering.
• Stick to Integers: The @scale = 4 trick eliminates floating-point precision errors entirely.
• Limit Recursion Depth: Since the maximum number of items needed is 4 (4*0.25x = 1x), setting depth <=4 prevents unnecessary recursion.

Option 2: Application-Level Backtracking (More Flexible & Performant) #

For larger datasets or more control over pruning, implement the logic in an application layer (e.g., Python, Java). Backtracking with smart pruning will outperform pure database queries here.

Example Python Implementation #

# Define targets and raw items
target_A = 60
target_B = 43
target_C = 34

items = [
    (1, 50, 20, 4),
    (2, 10, 40, 10),
    (3, 16, 9, 30),
    (4, 4, 3, 14)
]

# Pre-generate valid candidates (convert to integers to avoid float errors)
scaling_factor = 4
scaled_target = (target_A * scaling_factor, target_B * scaling_factor, target_C * scaling_factor)

candidates = []
for item_id, a, b, c in items:
    # 1x multiplier (scaled by 4)
    candidates.append( (item_id, a*scaling_factor, b*scaling_factor, c*scaling_factor, 1.0) )
    # 0.5x multiplier (scaled to 2x original)
    scaled_a = a * 2
    scaled_b = b * 2
    scaled_c = c * 2
    if scaled_a <= scaled_target[0] and scaled_b <= scaled_target[1] and scaled_c <= scaled_target[2]:
        candidates.append( (item_id, scaled_a, scaled_b, scaled_c, 0.5) )
    # 0.25x multiplier (scaled to 1x original)
    scaled_a = a * 1
    scaled_b = b * 1
    scaled_c = c * 1
    if scaled_a <= scaled_target[0] and scaled_b <= scaled_target[1] and scaled_c <= scaled_target[2]:
        candidates.append( (item_id, scaled_a, scaled_b, scaled_c, 0.25) )

matched_combinations = []

def backtrack(start_idx, current_sum, used_items):
    a_sum, b_sum, c_sum = current_sum
    # Check if we've hit the target
    if (a_sum, b_sum, c_sum) == scaled_target:
        matched_combinations.append(used_items.copy())
        return
    # Prune paths that exceed any target
    if a_sum > scaled_target[0] or b_sum > scaled_target[1] or c_sum > scaled_target[2]:
        return
    # Iterate through remaining candidates
    for i in range(start_idx, len(candidates)):
        item_id, a, b, c, mul = candidates[i]
        # Skip if we've already used this item
        if item_id in used_items:
            continue
        # Add the item to the current combination
        used_items[item_id] = mul
        # Recurse with next candidate
        backtrack(i + 1, (a_sum + a, b_sum + b, c_sum + c), used_items)
        # Remove the item (backtrack step)
        del used_items[item_id]

# Start backtracking from first candidate
backtrack(0, (0, 0, 0), {})

# Print results
print("Matched combinations:")
for combo in matched_combinations:
    print(", ".join([f"Item{id} x{mul}" for id, mul in combo.items()]))

Advantages of Application-Level Approach: #

• Better Pruning: You can add custom logic to skip entire branches (e.g., if the remaining candidates can't make up the difference to the target).
• No Database Limitations: Works with any MySQL version and avoids recursion depth limits.
• Easier Debugging: You can step through the code to tweak logic or adjust filtering.

Final Recommendations #

• For small datasets or if you want to keep logic in the database, use the MySQL recursive CTE approach (with integer scaling to avoid float errors).
• For larger datasets (150+ items) or more control, go with the application-level backtracking solution—it's faster and more flexible.

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