Может ли этот жадный алгоритм быть более эффективным? - PullRequest
Новая
       5

Может ли этот жадный алгоритм быть более эффективным?

2 голосов
/ 18 сентября 2019

Я готовлюсь к экзамену и готовлюсь к задаче, которая требует от меня реализации жадного алгоритма.

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

Пример: если у меня есть веса {53, 21, 40, 10, 18}, я не могу поставить 40 выше 21, потому что стопка должна быть в порядке убывания, иЯ не могу поставить 21 выше 40, потому что это не соответствует порядку.Оптимальное решение будет иметь кучу 1: 53, 21, 10 и кучу 2: 40 18

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

Мой вопрос, есть ли способ свести это к O (n)или O (nlogn)?Если есть, я просто не вижу этого и нуждаюсь в помощи.

Ответы [ 2 ]

3 голосов
/ 19 сентября 2019

Ваш алгоритм даст правильный результат.

Теперь обратите внимание на следующее: при посещении свай по порядку и остановке у первого, где может быть сложено следующее значение, у вас всегда будет ситуация, когда стопки упорядочены по их текущему верхнему (последнему) значению., в порядке возрастания.

Вы можете использовать это свойство, чтобы избежать итерации куч «слева направо».Вместо этого используйте бинарный поиск среди куч, чтобы найти первую кучу, которая может принять следующее значение.

Это даст вам O (nlogn) времясложность.

2 голосов
/ 19 сентября 2019

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

Рассмотрим самую длинную возрастающую подпоследовательность (LIS) массива.Поскольку элементы по возрастанию в индексе, а также по возрастанию в значении, все они должны быть в разных кучах.В результате минимальное количество необходимых куч равно числу элементов в LIS.

LIS легко решается в O(NlogN) с использованием динамического программирования и двоичного поиска.

Обратите внимание, чтоалгоритм, который вы описываете, делает то же самое, что и алгоритм ниже - он находит первую стопку, в которую вы можете поместить элемент (с помощью бинарного поиска), или создает новую стопку, так что это служит «доказательством» правильности вашего алгоритмаи способ уменьшить вашу сложность.

Пусть dp[i] будет равен элементу минимального значения в конце возрастающей подпоследовательности длины (i + 1).Чтобы перефразировать его с точки зрения вашего вопроса, dp[i] также будет равен весу камня в куче ith. 

from bisect import bisect_left
def lengthOfLIS(nums):

    arr = []

    for i in range(len(nums)):
        idx = bisect_left(arr, nums[i])
        if idx == len(arr):
            arr.append(nums[i])
        else:
            arr[idx] = nums[i]
    return len(arr)
...