найти подмножество с элементами меньше S - PullRequest
Новая
       59

найти подмножество с элементами меньше S

0 голосов
/ 27 февраля 2019

Мне нужно найти алгоритм для следующей задачи:

Вводятся два числа S и k натуральных чисел и несортированный набор из n попарно различных чисел.

решить вO (n), если существует подмножество из k чисел, которые суммируются до <= S.Примечание: k не должно быть частью временной сложности. </p> 

algorithm({x_1, ..., x_n}, k, S):
    if exists |{x_i, ..., x_j}| = k and x_i + ... x_j <= S return true

Я не нахожу решение с временной сложностью O (n).

То, что я смог получить, находится вO (kn), когда мы ищем k, умноженное на минимум, а сумма увеличивается: 

algorithm(a={x_1, ..., x_n}, k, S):
    sum = 0
    for i=1,...,k:
        min = a.popFirst()
        for i=2,...,len(a):
            if(a[i] < min):
                t = a[i]
                a[i] = min
                min = t
        sum += min
    if sum <= S:
        return true
    else:
        return false

, это в O (n) и возвращает правильный результат.Как я могу потерять k?

Спасибо за помощь, я действительно борюсь с этим!

Ответы [ 2 ]

0 голосов
/ 27 февраля 2019

Быстрый выбор можно использовать для поиска k мельчайших элементов: https://en.wikipedia.org/wiki/Quickselect

Это в основном быстрая сортировка, за исключением того, что вы выполняете рекурсивный анализ только на интересной стороне пивота.

Простая реализация выполняется за O (N) ожидаемое время, но, используя медиану медиан для выбора оси, вы можете сделать это реальной границей наихудшего случая: https://en.wikipedia.org/wiki/Median_of_medians

0 голосов
/ 27 февраля 2019

Вы можете построить минимальную кучу размером k из набора.Временная сложность построения составляет O(n) ожидаемое время и O(n log k) наихудший случай.Куча должна содержать первые k минимальные элементы из набора.

Тогда будет просто увидеть, что сумма элементов в куче равна <= S.Вам не нужно удалять элементы из кучи, чтобы вычислить сумму.Просто пройдите кучу, чтобы вычислить сумму.Удаление всех элементов влечет за собой k log k сложность.

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

...