一个简单的加法问题

一个简单的加法问题，实现起来，又比想象的复杂。

问题

之前有个想法，抽象之后，就是简单的加法问题。

问题是这样的。用户有个得分，而用户可能做了不同的选择，对应不同的选择可以得到不同的分数，那么，是否有可能计算出用户做了哪些选择？

办法

简单一想，这不就是一个加法问题吗？

比如选择的分数为3分，5分，6分。
如果用户得了8分，就是5+3，那么用户就是选择了3分和5分。
如果用户得了9分，那么可能是3+3+3，也可能是3+6。所以有两种可能。

这样一想，觉得很简单，就是一个循环问题，不停的相加，最终计算出所有可能的结果就可以了。

由于现在流行让ai写代码，于是就将问题描述给了ai，让其生成代码。
ai直接给了个递归的代码，初步一看，还没看懂。

# 等级映射关系，键为数值，值为等级名称
level_mapping = {10: 'low', 20: 'medium'}

def find_combinations(target, current_combination, start_index):
    # 当目标值为 0 时，说明找到了一种有效的组合
    if target == 0:
        return [current_combination.copy()]
    combinations = []
    # 从 start_index 开始遍历等级映射的数值
    for i in range(start_index, len(list(level_mapping.keys()))):
        value = list(level_mapping.keys())[i]
        # 如果当前数值小于等于目标值，则可以继续尝试添加
        if value <= target:
            current_combination.append(value)
            # 递归调用，继续寻找组合
            sub_combinations = find_combinations(target - value, current_combination, i)
            combinations.extend(sub_combinations)
            # 回溯，移除最后添加的数值，尝试其他组合
            current_combination.pop()
    return combinations

def calculate_diff_combinations(diff_values):
    all_combinations = {}
    for diff in diff_values:
        # 找出该 diff 值的所有组合
        combinations = find_combinations(diff, [], 0)
        named_combinations = []
        for comb in combinations:
            # 将数值组合转换为等级名称组合
            named_comb = [level_mapping[value] for value in comb]
            named_combinations.append(named_comb)
        all_combinations[diff] = named_combinations
    return all_combinations

# 示例 diff 值列表
diff_values = [10, 20, 30]
result = calculate_diff_combinations(diff_values)
# 输出每个 diff 值对应的所有可能组合
for diff, combos in result.items():
    print(f"Diff {diff} 可能的组合: {combos}")

拿样例试了一下，确实可以分解。
输入实际数据，发现程序一直在跑，程序一直在分解比较小的数。而实际的区间是一个非常大的区间，样本中最小的是个位数，最大的是5位数。
这样由个位数一直累加到5位数，不知道要多久。

考虑限制数量，在实际这个场景中，用户不太可能比如选10个2分的，因此考虑限制组合中单个选项出现的次数以及组合的长度。比如100分，不太可能是50个2分相加，而更可能是21+79。这里我们假定选项中有21和79这样的选项。（实际情况是大部分样本可以覆盖，还是有一些样本无法计算出组合。）

另一个优化是，先计算大的数据，比如，100分，可能是79+21，而不是2+2+2+...+2这样，优先计算大的数据。
再次运算之后，发现组合的数据还是庞大。考虑实际的场景，选择一个组合即可，不需要非常精确地考虑所有的组合，因此，一旦找到一个符合条件的组合，就结束寻找。

但是，带入实际数据之后，还是运行了很长时间。
因为，选项的组合有30个，这样数量级是非常大的。还考虑了做一个彩虹表来查询，比如1个组合是30个，2个的组合是30x30，3个组合是30x30x30，再往后，觉得这个数量级太大了，实际情况可能不太可能出现里面的一些情况。

因此，还是使用原来的方法，将组合数缩短到5，经过一段时间的计算，大部分结果算出来了。

def find_combinations(target, current_combination, start_index, level_counts):
    # 当目标值为 0 且组合长度不超过 5 时，说明找到了一种有效的组合
    if target == 0 and len(current_combination) <= 5:
        return [current_combination.copy()]
    # 从较大的数值开始遍历等级映射
    sorted_level_values = sorted(level_mapping.keys(), reverse=True)
    for i in range(start_index, len(sorted_level_values)):
        value = sorted_level_values[i]
        level_name = level_mapping[value]
        # 检查该等级的使用次数是否超过 5 次，且当前组合长度加上 1 不超过 5
        if level_counts.get(level_name, 0) < 6 and value <= target and len(current_combination) + 1 <= 6:
            current_combination.append(value)
            # 更新该等级的使用次数
            level_counts[level_name] = level_counts.get(level_name, 0) + 1
            # 递归调用，继续寻找组合
            sub_combinations = find_combinations(target - value, current_combination, i, level_counts)
            if sub_combinations:
                # 如果找到有效组合，直接返回
                return sub_combinations
            # 回溯，移除最后添加的数值
            current_combination.pop()
            # 回溯，恢复该等级的使用次数
            level_counts[level_name] -= 1
    return []

def calculate_diff_combinations(diff_values):
    all_combinations = {}
    for diff in diff_values:
        # 初始化每个等级的使用次数为 0
        level_counts = {level: 0 for level in level_mapping.values()}
        # 找出该 diff 值的所有组合
        combinations = find_combinations(diff, [], 0, level_counts)
        named_combinations = []
        for comb in combinations:
            # 将数值组合转换为等级名称组合
            named_comb = [level_mapping[value] for value in comb]
            named_combinations.append(named_comb)
        all_combinations[diff] = named_combinations
    return all_combinations

最终计算出了大部分数据。

然而还有一些比如5位数的数据，没有计算出来。

让ai再写一个代码，结果直接运行超过了递归的长度。于是增加一个排序，让代码先从大的开始找，并且限制了长度。

sorted_scores = sorted(level_mapping.keys())

def find_combination(target, scores):
    stack = [(target, [], 0)]
    attempt_count = 0
    while stack:
        current_target, current_combination, start_index = stack.pop()
        attempt_count += 1
        # 输出中间尝试的进度信息
        print(f"第 {attempt_count} 次尝试，当前组合: {[level_mapping[score] for score in current_combination]}，剩余目标分数: {current_target}")
        if current_target == 0 and len(current_combination) < 15:
            return current_combination
        if current_target < 0 or len(current_combination) >= 15:
            continue
        for i in range(start_index, len(scores)):
            new_target = current_target - scores[i]
            new_combination = current_combination + [scores[i]]
            stack.append((new_target, new_combination, i))
    return None

最终，经过200多万次的尝试，成功分解出了对应的参数。

一道看起来非常简单的算式，实际运行需要不断优化剪枝。

学习了一下，原来是个回溯算法。