带Fixed固定元素必选约束的子集和问题Python实现求助

核心错误点 #

• 固定值扣除逻辑错误：Fixed的总和是固定要计入最终结果的，仅需要在计算可变元素的目标和时扣除一次，你现在每次递归选中元素时都会重复扣除Fixed总和，相当于固定值被多扣了N次，自然无法匹配到正确结果。
• 递归边界逻辑错误：你当前的逻辑仅能匹配“可变元素和刚好等于目标值”的场景，且剩余目标小于1时直接返回None，没有考虑我们可以接受“和小于等于目标值的最优解”的需求。
• 没有预先计算可变元素的最大允许和：你的测试用例中Fixed总和为3+2=5，总Target为8，因此可变元素的目标和应为8-5=3，这一步需要预先计算，不需要传入递归逻辑重复计算。

修正后代码 #

import pandas as pd

Fixed = pd.Series([3,2])
Variable = pd.Series([15,1,4,6,3,10])
Target = 8

def subsetsum(Variable, target_variable):
    # 边界条件：如果可变目标已经小于等于0，直接返回空列表（不选任何元素）
    if target_variable <= 0:
        return []
    # 没有可选元素了，返回空列表
    if len(Variable) == 0:
        return []
    current = Variable.iloc[0]
    # 选当前元素的情况
    if current <= target_variable:
        with_v = [current] + subsetsum(Variable.iloc[1:], target_variable - current)
        # 计算选当前元素的总和，和不选的情况对比，取更接近目标的
        sum_with = sum(with_v)
        without_v = subsetsum(Variable.iloc[1:], target_variable)
        sum_without = sum(without_v)
        # 优先返回更接近目标的，相等的话返回先找到的（也就是选当前元素的）
        if sum_with >= sum_without:
            return with_v
    # 不选当前元素的情况
    return subsetsum(Variable.iloc[1:], target_variable)

# 先计算可变元素的最大允许和
fixed_sum = Fixed.sum()
max_variable = Target - fixed_sum
# 可变元素允许和不能小于0
if max_variable < 0:
    print("固定值总和已经超过目标值，无符合条件解")
else:
    selected_variable = subsetsum(Variable, max_variable)
    print("选中的可变元素：", selected_variable)
    print("最终总和：", fixed_sum + sum(selected_variable))

测试结果 #

运行上述代码后输出：

选中的可变元素： [3]
最终总和： 8

完全符合预期结果。

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