总和大于或等于 k 的最小子集
Smallest subset with sum greater or equal to k
我试图找到一个分而治之的算法来解决 O(n) 中的这个问题，但我没有找到任何东西。
给定数组 A 和给定值 k。
找到总和大于或等于 k 的最小子集。
有人可以给我一个开始解决问题的想法吗？
非常感谢任何帮助。
对数组进行排序，然后从大到小选择元素，直到和足够大。这种方法的时间复杂度为 O(n log n).
当希望找到一个小的子集时，可以通过使用快速排序算法而不对较低的分区进行排序来实现较低的平均时间复杂度，除非并且直到证明有必要这样做；当在较高分区中发现和足够大的子集时，可以忽略较低分区。如果子集的预期大小与 n 无关，那么这种方法的时间复杂度应该是 O(n)。
使用快速选择在预期的线性时间内执行此操作。
您的第一个快速选择会将数组分成两部分，一个包含较大的元素，另一个包含较小的元素。如果较大元素的总和 > k，则对其进行迭代。否则，以 k - sum(larger elements) 为目标迭代另一半。
我试图找到一个分而治之的算法来解决 O(n) 中的这个问题，但我没有找到任何东西。 给定数组 A 和给定值 k。 找到总和大于或等于 k 的最小子集。 有人可以给我一个开始解决问题的想法吗？
非常感谢任何帮助。
对数组进行排序，然后从大到小选择元素，直到和足够大。这种方法的时间复杂度为 O(n log n).
当希望找到一个小的子集时，可以通过使用快速排序算法而不对较低的分区进行排序来实现较低的平均时间复杂度，除非并且直到证明有必要这样做；当在较高分区中发现和足够大的子集时，可以忽略较低分区。如果子集的预期大小与 n 无关，那么这种方法的时间复杂度应该是 O(n)。
使用快速选择在预期的线性时间内执行此操作。
您的第一个快速选择会将数组分成两部分，一个包含较大的元素，另一个包含较小的元素。如果较大元素的总和 > k，则对其进行迭代。否则，以 k - sum(larger elements) 为目标迭代另一半。