Найдите минимальное количество необходимых элементов, чтобы их сумма равнялась или превышала S

Question

Я знаю, что это можно сделать, отсортировав массив и взяв большие числа, пока не будет выполнено необходимое условие. Это займет как минимум nlog (n) время сортировки.

Есть ли улучшения по сравнению с nlog(n).

Мы можем предположить, что все числа положительны.

Answer 1

Вот алгоритм, O(n + size(smallest subset) * log(n)).Если наименьшее подмножество намного меньше, чем массив, это будет O(n).

Чтение http://en.wikipedia.org/wiki/Heap_%28data_structure%29, если мое описание алгоритма неясно (оно легкое на деталях, но деталивсе там).

1. Превратить массив в кучу так, чтобы самый большой элемент был доступен за время O(n).
2. Повторно извлекать самый большой элемент из кучи до их суммыдостаточно велик.Это займет 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.

Answer 2

Предполагая, что числа являются целыми числами, вы можете улучшить обычную n lg(n) сложность сортировки, поскольку в этом случае у нас есть дополнительная информация о том, что значения находятся в диапазоне от 0 до S (для наших целей целые числа, большие, чем S, одинаковы как S).

Поскольку диапазон значений конечен, вы можете использовать несравнительный алгоритм сортировки, такой как Sigeonhole Sort или Radix Sort , чтобы опуститься ниже n lg(n).

Обратите внимание, что эти методы зависят от некоторой функции S, поэтому, если S становится достаточно большим (а n остается достаточно маленьким), вам лучше вернуться к сравнительной сортировке.

Answer 3

Вот O (n) ожидаемое время решения проблемы.Это похоже на идею Морона, но мы не выкидываем работу, которую выполнял наш алгоритм выбора на каждом шаге, и мы начинаем пробовать элемент потенциально посередине, а не использовать повторяющийся метод удвоения.

В качестве альтернативы, это просто быстрый выбор с небольшим дополнительным бухгалтерским учетом на оставшуюся сумму.

Во-первых, ясно, что если бы у вас были элементы в отсортированном порядке, вы могли бы сначала выбрать самые большие элементы, пока не превысите желаемую сумму.Наше решение будет таким, за исключением того, что мы будем стараться изо всех сил, чтобы не находить информацию о заказе, потому что сортировка медленная.

Вы хотите иметь возможность определить, является ли данное значениеотрезать.Если мы включим это значение и все, что больше его, мы встретим или превысим 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)  

Answer 4

Одним из улучшений (асимптотически) по сравнению с тэтой (nlogn), которое вы можете сделать, является получение алгоритма времени O (n log K), где K - требуемое минимальное количество элементов.

Таким образом, если K постоянноили, скажем, лог n, это лучше (асимптотически), чем сортировка.Конечно, если K - это n ^ epsilon, то это не лучше, чем Theta (n logn).

Способ сделать это - использовать алгоритмы выбора , которые могут сказать вам, что я ^th самый большой элемент за время O (n).

Теперь выполните бинарный поиск для K, начиная с i = 1 (самое большое) и удваивая i и т. Д. На каждом ходу.

Вы находите наибольшее значение i ^th , находите сумму самых больших элементов i и проверяете, больше ли оно S или нет.

Таким образом, вы выполняете O (log K) прогоны алгоритма выбора (который является O (n)) для общего времени прогона O (n log K).

Answer 5

1. исключить числа голубиная дыра сортирует числа

Суммируйте элементы сверху вниз в отсортированном порядке, пока не превысите S.