从变量集合中寻找特定和值的Python算法实现需求

核心思路 #

因为要处理至少两位小数的精确匹配，直接用浮点数计算会存在精度误差，所以第一步将所有数值和目标值乘以100转为整数，把问题转化为整数子集和问题，彻底规避精度问题。

针对「返回首个解」和「返回全部解」的不同需求，采用回溯+剪枝方案，在30个元素的规模下，合理剪枝能大幅提升运行效率。

代码实现 #

工具函数：精度转换 #

def convert_to_int(numbers, target):
    # 转整数：乘以100后取整，确保两位小数精度
    int_numbers = [round(num * 100) for num in numbers]
    int_target = round(target * 100)
    return int_numbers, int_target

查找首个可行解 #

def find_first_subset(numbers, target):
    int_numbers, int_target = convert_to_int(numbers, target)
    n = len(int_numbers)
    # 排序便于剪枝
    sorted_nums = sorted(int_numbers)
    path = []

    def backtrack(index, current_sum):
        if current_sum == int_target:
            # 转回原数值格式
            return [num / 100 for num in path.copy()]
        if index >= n:
            return None
        
        # 选择当前元素
        path.append(sorted_nums[index])
        res = backtrack(index + 1, current_sum + sorted_nums[index])
        if res is not None:
            return res
        # 不选当前元素
        path.pop()
        
        # 剪枝：若当前元素为正数，后续元素更大，累加只会超过目标，直接跳过分支
        if sorted_nums[index] > 0 and current_sum + sorted_nums[index] > int_target:
            return None
        
        return backtrack(index + 1, current_sum)
    
    return backtrack(0, 0)

查找全部可行解 #

def find_all_subsets(numbers, target):
    int_numbers, int_target = convert_to_int(numbers, target)
    n = len(int_numbers)
    sorted_nums = sorted(int_numbers)
    result = []
    path = []

    def backtrack(index, current_sum):
        if current_sum == int_target:
            result.append([num / 100 for num in path.copy()])
            return
        if index >= n:
            return
        
        # 选择当前元素
        path.append(sorted_nums[index])
        backtrack(index + 1, current_sum + sorted_nums[index])
        path.pop()
        
        # 剪枝：正数分支超目标则直接跳过
        if sorted_nums[index] > 0 and current_sum + sorted_nums[index] > int_target:
            return
        
        backtrack(index + 1, current_sum)
    
    backtrack(0, 0)
    return result

使用示例 #

# 测试示例
numbers = [-2, -1, 1, 2, 3, 5, 8, 10]
target = 6

# 获取首个解
first_solution = find_first_subset(numbers, target)
print("首个解:", first_solution)  # 输出示例：[-2.0, 8.0]

# 获取全部解
all_solutions = find_all_subsets(numbers, target)
print("全部解:")
for sol in all_solutions:
    print(sol)

注意事项 #

• 针对30个元素的集合，查找全部解可能耗时较长（理论上是2^30级别的遍历），但排序剪枝能有效减少无效分支；若集合中负数较多，可额外计算剩余元素的总和，判断是否有可能达到目标来进一步优化剪枝逻辑。
• 转换整数时使用round()，确保两位小数的精确转换，避免浮点数存储误差导致的匹配失败。

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