解决“从一组数中找到一些数字，使和等于特定值”的小工具

[zyx199199]

去年底帮公司整理年度财务数据时，遇到一个问题：

一个员工的几笔报销加起来一共几千块，已经一次性给员工报销掉了，但是到年底整理财务数据时，发现已经无法将当时那笔报销款与发票对应上了。

实际上只要找到哪几张发票的金额总和大体上约等于那笔报销款就行，因为发票是后来找了好几张凑出来的，所以也不是正好等于那笔报销款。印象中是相差了十几块钱。

我当初傻傻地人工对照整理了好几十分钟，才确定下来。

前两个月又想起来这个事，上网搜了下有没有好的解决方案，发现用 Excel 能勉强求解。但是 Excel 求解有两个问题：

• 一次性只能从大概最多 50~60 个候选数字中求解，超过这个范围 Excel 直接提示无法计算。这个我勉强刚好满足，就是耗时久一点
• 一次只能设置一个目标和。这个有点麻烦，因为我需要找的目标和不是一个数字，而是一个范围。

所以我自己写了个 Google Sheets 的插件。不知道有没有人有类似的需求。

插件地址： https://workspace.google.com/marketplace/app/add_up_to/1020284067440

我这个插件支持：

• 几百上千个候选数字中求解
• 一次设置多个目标值，为每个目标值求解

[coolzqy]

def find_closest_sum_dp(numbers, target):
dp = {0: []}

for num in numbers:
new_dp = dp.copy()
for partial_sum, combo in dp.items():
new_sum = partial_sum + num
if new_sum not in dp or abs(target - new_sum) < abs(target - partial_sum):
new_dp[new_sum] = combo + [num]
dp = new_dp

closest_sum = min(dp, key=lambda x: abs(target - x))
return dp[closest_sum]

numbers = [1, 2, 3, 4, 5]
target = 9
result = find_closest_sum_dp(numbers, target)
print(result)