algorithm - 总和大于或等于 k ​​的最小子集

Question

我试图找到一种分而治之的算法来解决 O(n) 中的这个问题，但我什么也没找到。给定一个数组 A 和给定值 k。找到总和大于或等于 k ​​的最小子集。有人可以给我一个开始解决问题的想法吗？

任何帮助深表感谢。

标签： algorithmdivide-and-conquer

Answer 1

使用快速选择在预期的线性时间内执行此操作。

您的第一个快速选择会将数组分成两部分，一个包含较大的元素，另一个包含较小的元素。如果较大元素的总和 > k，则对其进行迭代。否则，以 k - sum（更大的元素）为目标对另一半进行迭代。