从账单列表生成总和为指定值的唯一组合的实现逻辑与方案问询

Hey there! Let's tackle this problem step by step. First, let's clarify your core requirements:

• Find all bill combinations from the given list where the total sum of amounts equals exactly 10000, keeping track of their corresponding bill IDs.
• If no such exact combinations exist, generate a list of combinations with at most 6 bills (we'll assume you want the combination whose sum is closest to 10000, since this makes the fallback requirement meaningful—feel free to adjust if you meant something else!).

First, let's fix the issues with your current code #

Your GetNumbers function uses a greedy approach that only picks 1-2 large values before returning, which is unreliable for subset-sum problems. Greedy algorithms often miss valid combinations (e.g., several smaller values that add up to the target, even if large values don't fit perfectly). We need a more thorough approach.

Solution 1: Find all exact sum combinations (sum = 10000) #

We'll use a backtracking algorithm to explore every possible subset of bills, ensuring we don't miss any valid combinations. This method recursively builds combinations and checks if their sum matches the target.

data = [ ["10000025", 710], ["1000138833", 1065], ["100274005", 820], ["1353180", 3160], ["481584", 3670], ["4851845845", 1690], ["485584", 1310], ["48848448", 1000], ["49849948", 1050], ["585598", 4620], ["84154858584", 620], ["841584584", 2050], ["8451184584", 2860], ["845188956", 1800], ["845845184", 1300], ["8458484", 2300], ["8954884", 1780], ["9416481584", 2720], ["9448155584", 1000], ["94949494", 1000], ["959494158", 1590], ["98558858", 1550] ]
target_sum = 10000

def find_exact_combinations(bill_data, target):
    valid_combinations = []
    
    def backtrack(start_idx, current_comb, current_total):
        # Base case: we've hit the target sum
        if current_total == target:
            valid_combinations.append([[bill[0], bill[1]] for bill in current_comb])
            return
        # Stop if we exceed the target or run out of bills
        if current_total > target or start_idx >= len(bill_data):
            return
        
        # Option 1: Include the current bill in the combination
        current_bill = bill_data[start_idx]
        backtrack(start_idx + 1, current_comb + [current_bill], current_total + current_bill[1])
        
        # Option 2: Skip the current bill and move to the next
        backtrack(start_idx + 1, current_comb, current_total)
    
    backtrack(0, [], 0)
    return valid_combinations

# Get all exact matches
exact_matches = find_exact_combinations(data, target_sum)

How this works: #

• The backtrack function recursively explores two choices for each bill: include it in the current combination, or skip it.
• When the sum of the current combination hits 10000, we save the full combination (with IDs and amounts).
• We stop recursing if the sum exceeds the target or we've checked all bills.

Solution 2: Fallback - Find best combination with at most 6 bills #

If no exact matches exist, we'll search for combinations of 1 to 6 bills whose sum is closest to 10000 (we'll prioritize sums that don't exceed the target; adjust the code if you want to allow sums over 10000).

from itertools import combinations

def find_best_fallback(bill_data, target, max_bills=6):
    best_sum = 0
    best_combination = []
    
    # Check all combinations of 1 to max_bills
    for bill_count in range(1, max_bills + 1):
        for comb in combinations(bill_data, bill_count):
            current_sum = sum(bill[1] for bill in comb)
            # If we hit the target exactly, return immediately
            if current_sum == target:
                return [list(bill) for bill in comb]
            # Update best combination if current sum is closer (and not over target)
            if best_sum < current_sum <= target:
                best_sum = current_sum
                best_combination = [list(bill) for bill in comb]
            # Uncomment below to allow sums over the target
            # elif current_sum > target and (current_sum - target) < (target - best_sum):
            #     best_sum = current_sum
            #     best_combination = [list(bill) for bill in comb]
    return best_combination

Putting it all together #

# Main execution flow
if exact_matches:
    print("Found combinations that sum to 10000:")
    for i, combo in enumerate(exact_matches, 1):
        print(f"Combination {i}: {combo}")
else:
    print("No exact combinations sum to 10000. Here's the best fallback with at most 6 bills:")
    fallback_combo = find_best_fallback(data, target_sum)
    print(fallback_combo)

Notes: #

• If your fallback requirement meant "combinations where the number of remaining (unselected) bills is at most 6", you can modify the fallback function to filter for len(data) - len(comb) <=6 instead of len(comb) <=6.
• With your dataset of 22 bills, the total number of combinations to check for the fallback is ~109k, which is totally manageable for Python.

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