Я знаю, что это может быть сделано путем сортировки массива и принятия больших чисел до тех пор, пока не будет выполнено требуемое условие. Это займет как минимум nlog (n) время сортировки.
Есть ли улучшения над nlog(n).
Можно считать, что все числа положительны.
Вот алгоритм O(n + size(smallest subset) * log(n)). Если наименьшее подмножество много меньше массива, это будет O(n).
Прочитайте http://en.wikipedia.org/wiki/Heap_%28data_structure%29, если мое описание алгоритма неясно (оно подробно освещено, но все детали там).
O(n).O(size(smallest subset) * log(n)).Это почти наверняка ответ, на который они надеялись, но не получить его не должно быть нарушителем сделки.
Изменить: Вот еще один вариант, который часто быстр, но может быть медленнее.
Walk through elements, until the sum of the first few exceeds S. Store current_sum.
Copy those elements into an array.
Heapify that array such that the minimum is easy to find, remember the minimum.
For each remaining element in the main array:
if min(in our heap) < element:
insert element into heap
increase current_sum by element
while S + min(in our heap) < current_sum:
current_sum -= min(in our heap)
remove min from heap
Если мы получим отказ от большей части массива без манипуляции с нашей кучей, это может быть вдвое быстрее, чем предыдущее решение. Но также возможно быть медленнее, например, когда последний элемент массива оказывается больше, чем S.
Предполагая, что числа являются целыми числами, вы можете улучшить обычную сложность сортировки n lg(n), поскольку в этом случае у нас есть дополнительная информация о том, что значения находятся между 0 и S (для наших целей целые числа, большие, чем S, одинаковы как S).
Поскольку диапазон значений конечен, вы можете использовать не сравнительный алгоритм сортировки, например Pigeonhole Sort или Radix Sort, чтобы перейти ниже n lg(n).
Обратите внимание, что эти методы зависят от некоторой функции S, поэтому, если S становится достаточно большим (и n остается достаточно маленьким), вам может быть лучше вернуться к сравнительному виду.
Одно улучшение (асимптотически) над Theta (nlogn), которое вы можете сделать, - это получить алгоритм времени O (n log K), где K - искомое минимальное количество элементов.
Таким образом, если K является константой или, скажем, log n, это лучше (асимптотически), чем сортировка. Конечно, если K n ^ epsilon, то это не лучше, чем Theta (n logn).
Способ сделать это - использовать алгоритмы выбора , которые могут рассказать вам о наибольшем элементе я th в O (n) времени.
Теперь выполните двоичный поиск для K, начиная с я = 1 (наибольший) и удвоения я и т.д. на каждом шагу.
Вы найдете наибольший я th и найдите сумму наибольших элементов я и проверьте, больше ли она S или нет.
Таким образом, вы должны выполнить O (log K) пробелы алгоритма выбора (который является O (n)) для общего времени работы O (n log K).
Здесь существует ожидаемое решение времени O (n). Это похоже на идею Морона, но мы не выбрасываем работу, которую наш алгоритм выбора выполнял на каждом шаге, и мы начинаем пытаться из элемента потенциально посередине, а не использовать метод повторного удвоения.
В качестве альтернативы, это действительно просто quickselect с небольшим дополнительным балансом для оставшейся суммы.
Во-первых, ясно, что если бы у вас были отсортированные по порядку элементы, вы могли бы просто выбрать самые большие предметы сначала, пока не превысите желаемую сумму. Наше решение будет таким, но мы стараемся изо всех сил стараться не обнаруживать информацию о заказе, потому что сортировка идет медленно.
Вы хотите, чтобы определить, является ли заданное значение обрезанным. Если мы включим это значение и все большее, чем оно, мы встретимся или превысим S, но когда мы его удалим, мы ниже S, тогда мы золотые.
Вот код psuedo, я не тестировал его для случаев с краем, но в этом есть идея.
def Solve(arr, s):
# We could get rid of worse case O(n^2) behavior that basically never happens
# by selecting the median here deterministically, but in practice, the constant
# factor on the algorithm will be much worse.
p = random_element(arr)
left_arr, right_arr = partition(arr, p)
# assume p is in neither left_arr nor right_arr
right_sum = sum(right_arr)
if right_sum + p >= s:
if right_sum < s:
# solved it, p forms the cut off
return len(right_arr) + 1
# took too much, at least we eliminated left_arr and p
return Solve(right_arr, s)
else:
# didn't take enough yet, include all elements from and eliminate right_arr and p
return len(right_arr) + 1 + Solve(left_arr, s - right_sum - p)
Суммируйте элементы с наивысшим наименьшим в отсортированном порядке до тех пор, пока вы не превысите S.