时间戳

首页 > 解决方案 > 在子集上定义的函数总和

algorithm - 在子集上定义的函数总和

问题描述

我想知道它们是否是解决以下问题的任何快速方法。我有数千个代码列表(A0, A1, A2, ...)。大约有一百万种不同的组合具有正值(A0-A1, A2-A10, A1-A2-A10, ...)。让值表示f(A0-A1)。请注意，并非所有组合都有附加值。

对于每个列出的组合，我想计算附加到包含给定组合的每个集合的值的总和。例如，对于A2-A10，计算

g(A2-A10) = f(A2-A10) + f(A1-A2-A10) + ...

我想以最小的时间复杂度做到这一点。一个更简单的相关问题是找到所有g(C)大于阈值的组合。

标签： algorithmtime-complexity

解决方案

使用位图对现有组合进行键控，其中位n表示 An是否在该特定编码中。将位图键控的值存储在您最喜欢的散列图结构中。因此，f(A0, A1, A10, A12) 将是combo_val[11000000001010000...]

要汇总所有所需的组合，请构建根的位图。例如，使用上面的组合，我们将有root = 1100000000101000（为了说明起见，总共截取 16 个元素。

现在只需循环遍历哈希图的键，root用作掩码。对所需值求和：

total = 0
for key in combo_val.keys()
    if root && key == root
        total += combo_val[key]

这会让你感动吗？

推荐阅读