Сумма подмножеств (динамическое программирование) в Python - проблема сложности - PullRequest
Новая
       37

Сумма подмножеств (динамическое программирование) в Python - проблема сложности

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

У меня есть проблема с некоторой реализацией функции, которая решает проблему суммы подмножеств в Python.

У нас здесь динамическое программирование, поэтому сложность должна быть полиномиальной.

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

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

Код на Python: 

def subsetsum(array,num):

    if num == 0 or num < 1:
        return None
    elif len(array) == 0:
        return None
    else:
        if array[0] == num:
            return [array[0]]
        else:
            with_v = subsetsum(array[1:],(num - array[0])) 
            if with_v:
                return [array[0]] + with_v
            else:
                return subsetsum(array[1:],num)

1 Ответ

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

Вы используете срезы для передачи суффиксов array, это создаст копию с линейным временем выполнения.Чтобы избежать этого, вы можете вместо этого передавать индексы.Еще одно преимущество заключается в том, что индексы можно хэшировать, поэтому вы можете кэшировать (или memoize ) и избегать повторного вычисления ответов: 

from functools import lru_cache

def ssum(array, N):
    @lru_cache(maxsize=None)
    def subsetsum(idx, num):
        if num < 1 or idx >= len(array):
            return frozenset()
        if array[idx] == num:
            return frozenset([idx])
        with_v = subsetsum(idx + 1, num - array[idx])
        if with_v:
            return with_v | frozenset([idx])
        else:
            return subsetsum(idx + 1, num)
    return list(array[i] for i in subsetsum(0, N))

>>> ssum([1,1,2], 4)
[1, 1, 2]

К сожалению, все еще стоит копировать полученный ответиз суффикса

...