Python递归实现预算物品组合查询：代码仅返回单一结果排查

核心问题分析 #

你的代码仅返回单一结果的直接原因是强制截断了结果集：

if len(results) > 0:
    results = [results[0]]

这行代码会丢弃所有符合预算的组合，只保留第一个。除此之外，代码还存在回溯逻辑不完整、近似组合处理混乱的问题。

修复后的完整代码 #

def find_combinations(items, target_sum, result_type='full'):
    # 按单价降序排序（可选，不影响结果完整性，仅优化递归优先级）
    items_sorted = sorted(items, key=lambda x: x[1], reverse=True)
    exact_results = []
    all_candidates = []  # 存储所有不超预算的组合及对应总花费

    def backtrack(start, remaining_budget, current_combination):
        # 记录当前组合的总花费
        total_spent = target_sum - remaining_budget
        all_candidates.append((current_combination.copy(), total_spent))
        
        if remaining_budget < 0:
            return
        if remaining_budget == 0:
            exact_results.append(current_combination.copy())
            return
        if start == len(items_sorted):
            return
        
        # 分支1：不购买当前物品，直接递归下一个物品
        backtrack(start + 1, remaining_budget, current_combination)
        
        # 分支2：购买1到最大可购买数量的当前物品
        item_name, price, max_count = items_sorted[start]
        for count in range(1, max_count + 1):
            cost = price * count
            if cost > remaining_budget:
                break  # 超过剩余预算，无需尝试更多数量
            current_combination.append((item_name, count))
            backtrack(start + 1, remaining_budget - cost, current_combination)
            current_combination.pop()  # 回溯，移除当前选择

    backtrack(0, target_sum, [])
    
    # 根据结果类型返回对应数据
    if result_type == 'full':
        # 优先返回所有精确匹配预算的组合
        if exact_results:
            return exact_results
        # 无精确匹配时，返回所有最接近预算的组合
        elif all_candidates:
            min_diff = min(abs(target_sum - spent) for _, spent in all_candidates)
            closest_results = [comb for comb, spent in all_candidates if abs(target_sum - spent) == min_diff]
            # 去重：避免不同递归路径生成相同组合
            unique_closest = []
            seen = set()
            for comb in closest_results:
                comb_tuple = tuple(sorted(comb))
                if comb_tuple not in seen:
                    seen.add(comb_tuple)
                    unique_closest.append(comb)
            return unique_closest
        else:
            return []
    elif result_type == 'most_items':
        if not all_candidates:
            return []
        # 过滤所有不超预算的组合
        valid_candidates = [comb for comb, spent in all_candidates if spent <= target_sum]
        if not valid_candidates:
            return []
        # 筛选物品总数最多的组合
        max_item_count = max(sum(count for _, count in comb) for comb in valid_candidates)
        most_items_results = [comb for comb in valid_candidates if sum(count for _, count in comb) == max_item_count]
        # 去重
        unique_most_items = []
        seen = set()
        for comb in most_items_results:
            comb_tuple = tuple(sorted(comb))
            if comb_tuple not in seen:
                seen.add(comb_tuple)
                unique_most_items.append(comb)
        return unique_most_items
    elif result_type == 'most_expensive':
        if not all_candidates:
            return []
        valid_candidates = [comb for comb, spent in all_candidates if spent <= target_sum]
        if not valid_candidates:
            return []
        # 筛选总花费最高的组合
        max_spent = max(spent for _, spent in all_candidates if spent <= target_sum)
        most_expensive_results = [comb for comb, spent in all_candidates if spent == max_spent]
        # 去重
        unique_most_expensive = []
        seen = set()
        for comb in most_expensive_results:
            comb_tuple = tuple(sorted(comb))
            if comb_tuple not in seen:
                seen.add(comb_tuple)
                unique_most_expensive.append(comb)
        return unique_most_expensive
    else:
        return exact_results if exact_results else []

关键修复点说明 #

1. 移除结果截断逻辑：删除了原代码中强制保留单个结果的语句，确保所有符合条件的组合都被保留。
2. 完善回溯逻辑：
   • 新增“不购买当前物品”的分支，覆盖所有可能的组合场景。
   • 使用copy()避免递归过程中组合列表被引用修改。
   • 当购买数量的花费超过剩余预算时直接终止循环，减少无效递归。
3. 优化近似组合处理：
   • 收集所有不超预算的组合，最后统一筛选最接近目标的组合，而非仅保留单个。
   • 添加组合去重逻辑，避免因递归路径不同生成重复组合。
4. 增强分支健壮性：每个result_type分支都处理了无结果的边界情况，保证代码稳定性。

使用示例 #

# 定义物品列表
items = [
    ["Sacred Foundry",12.69,2],
    ["Bloodstained Mire",26.55,2],
    ["Wooded Foothills",25.97,2],
    ["Verdant Catacombs",14.54,2],
    ["Fury",32.64,4]
]

# 获取所有最接近100欧元的组合
closest_combinations = find_combinations(items, 100, 'full')
for idx, comb in enumerate(closest_combinations, 1):
    # 计算组合总花费
    total = sum(price * count for name, count in comb for item in items if item[0] == name)
    print(f"组合{idx}: {comb}，总花费: {total:.2f}欧元")

内容的提问来源于stack exchange，提问作者Michaël