algorithm - 贪心算法按顺序查找潜在的加权事件？

Question

例如，假设有一个事件列表 {a, b, c, d, e, f, g}

a & b are worth 9 points each. c is worth 8 points. d & e are worth 6 points each. f is worth 5 points.g is worth 4 points.

事件列表已经按点降序排列。

我想找到满足特定要求(例如 F(X) = true)的三个事件的最高分组合(我们称此组合为 X)。

F(X)只接受三个事件的组合，不能修改。

如何生成 X 而不必首先计算所有可能的组合？
如何遍历所有可能的组合以减少总分？

我希望能够找到最高点组合，测试一下。如果失败，生成次高点组合等。

示例列表只有几项。但是，实际列表可能会变得非常大，并且生成所有组合是不切实际的。

我应该怎么做？

Answer 1

下面的想法只解决了一个更简单的问题版本，但也许可以扩展到更强大的解决方案。

设 [a(1)..a(N)] 为输入数组。我在这里建议的是一种从完整枚举中的 C(N,3)~N^3 个三元组中枚举前 N^(1/3) 个三元组的方法。我知道这是适度的，但它保证了 O(N) 的时间和空间。

1. s = a(1) + a(2) + a(N^(1/3))
2. T = [a(1),a(2), .. ,a(N^(1/3))] 中的所有三元组(占用 O(N) 时间和空间)
3. 按三元组和降序对 T 进行排序(时间复杂度:O(N^(1/3) * log N) = O(N))
4. 遍历 T 并返回每个三元组 r 而 sum(r) >= s

解释:

在 (1) 中，我们计算不涉及 T = [a(1)..a(N^(1/3))] 中项目的三元组的最高分。换句话说，T 已经包含了 score > s 的所有三元组。因此，我们生成 T 中的所有三元组，对它们进行排序，并仅返回我们确定的(即得分>=s 的)。将返回多少个这样的三胞胎？嗯，这取决于数组值，但我们可以保证至少有 N^(1/3) - 2 个三元组，因为所有三元组 [a(1)+a(2)+a(i)] 对于 2<i<=N^(1/3)总和> = s。在实践中，“好”三胞胎的数量可能要高得多，但这同样取决于阵列数量的分布。