寻找针对这种特定情况的子集和问题的解决方案（在 C# 或其他算法中）：
1) 集合中大约有 1,000 个数字（可能会增长到几千个）
2) 总额达到数十亿
3) 数字是货币值，所以有两位小数的精度（例如 2,345.17）
4）集合中的数字可以是正数和负数（所以处理净和）
然后我需要重复此搜索（使用相同的数字集）但总和不同，最多 1,000 次。最后整个过程运行 1000 次。因此，我们正在查看 1,000,000 次运行。目标是在 2 分钟内完成。这意味着每次运行不应超过 0.12 毫秒。
这可行吗？
-克里普
I'm going to assume you already know about the DP pseudo-poly algorithm, which is pretty much the only remotely (for optimal answers) tractable way to do this for 1,000 elements
The way the algorithm is usually implemented involves an array of size of the maximum sum, each representing a different bucket for the number at that index. To adapt this to decimals, you're going to need to transform your data from decimal to integer (by multiplying by 100). You could also implement this using a set data structure, which may be much easier and space efficient.
e.g.,
import copy
j = {0:1}
lst = [1,2,8,2.3,214]
for i in lst:
newj = copy.copy(j)
for k in j:
newj[k+i]=1
j = newj
Repeating the sub-set sum algorithm with a different sum shouldn't be an issue - if you follow the DP algorithm, you'll compute all the possible sums once and then you can recheck your set for the new sum each time.
The real issue is going the size of your set since it will grow as the algorithm progresses. In the worse pathological case, the size of the set will grow exponentially with the number of elements (every sum is unique, 2^n elements). If there is some overlap, you'll be better off. I'm guessing for 1000 elements though, with a large range, you might be in trouble.