如何用Python将浮点数列表分割为和在指定区间的唯一子列表？

问题说明 #

给定一个包含N个正浮点数的列表（N≤50），所有元素均处于区间[X,Y]（X、Y为正数，Y≤100），需要将列表分割为任意长度的子列表，要求每个子列表的元素和落在[X,Y]区间内，每个元素仅能出现在一个子列表中。

实现方案 #

由于数据规模较小，我们可以使用回溯法暴力尝试所有可能的分割方式，确保找到合法解。同时需要处理浮点数的精度问题，避免因浮点运算误差导致的错误判断。

代码实现 #

def split_list(data, X, Y):
    # 辅助函数：判断子列表和是否符合区间要求（允许1e-6的精度误差）
    def is_valid_sum(s):
        return X - 1e-6 <= s <= Y + 1e-6

    result = []
    total_elements = len(data)

    def backtrack(current_index):
        # 所有元素处理完成，返回成功
        if current_index == total_elements:
            return True
        
        current_num = data[current_index]
        # 先尝试将当前元素加入已有的子列表
        for sublist in result:
            new_sum = sum(sublist) + current_num
            if is_valid_sum(new_sum):
                sublist.append(current_num)
                if backtrack(current_index + 1):
                    return True
                # 回溯：撤销当前操作
                sublist.pop()
        
        # 尝试新建一个子列表（元素自身符合区间要求，题目已保证）
        result.append([current_num])
        if backtrack(current_index + 1):
            return True
        # 回溯：撤销新建操作
        result.pop()
        
        return False

    # 启动回溯，必然能找到解（因为每个元素单独成子列表都是合法的）
    backtrack(0)
    return result

使用示例 #

以题目给出的测试列表为例，设定X=20，Y=40：

data = [9.99, 12.50, 13.49, 9.99, 11.99, 16.34, 39.99, 24.99, 32.99, 25.99, 14.99]
X = 20
Y = 40

split_result = split_list(data, X, Y)
# 格式化输出结果
for idx, sublist in enumerate(split_result, 1):
    sub_sum = sum(sublist)
    print(f"子列表{idx}: {sublist}，元素和：{sub_sum:.2f}")

注意事项 #

1. 浮点数精度处理：通过引入1e-6的误差范围，避免因浮点数相加的精度问题（如0.1+0.2=0.30000000000000004）导致的错误判断。
2. 回溯逻辑：优先尝试将元素加入已有子列表，再考虑新建子列表，能更快收敛到合法解。
3. 解的存在性：题目明确所有元素均处于[X,Y]区间，因此每个元素单独作为子列表都是合法解，函数必然返回有效结果。

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