Рубрики

Программа Python для решения проблемы подмножества сумм | DP-25

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

Input:  set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output:  True  //There is a subset (4, 5) with sum 9.

# Рекурсивное решение для суммы подмножеств
# проблема

  
# Возвращает true, если есть подмножество
# множества [] с солнцем, равным данной сумме

def isSubsetSum(set, n, sum) :

    

    # Базовые случаи

    if (sum == 0) :

        return True

    if (n == 0 and sum != 0) :

        return False

   

    # Если последний элемент больше чем

    # сумма, затем проигнорируйте это

    if (set[n - 1] > sum) :

        return isSubsetSum(set, n - 1, sum);

   

    # еще, проверьте, можно ли получить сумму

    # любым из следующих

    # (a) включая последний элемент

    # (б) исключая последний элемент

    return isSubsetSum(set, n-1, sum) or isSubsetSum(set, n-1, sum-set[n-1])

      

      
# Программа драйвера для проверки вышеуказанной функции

set = [3, 34, 4, 12, 5, 2]

sum = 9

n = len(set)

if (isSubsetSum(set, n, sum) == True) :

    print("Found a subset with given sum")

else :

    print("No subset with given sum")

      
# Этот код предоставлен Никитой Тивари.

Выход:

Found a subset with given sum

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

python3

# Динамическое программирующее решение для задачи с суммой подмножеств
# Возвращает true, если есть подмножество
# set [] с солнцем, равным заданной сумме

  
# Возвращает true, если есть подмножество set []
# с солнцем, равным данной сумме

def isSubsetSum(set, n, sum):

      

    # Значение подмножества [i] [j] будет

    # true, если есть

    # подмножество множества [0..j-1] с суммой, равной i

    subset =([[False for i in range(sum + 1)] 

            for i in range(n + 1)])

      

    # Если сумма равна 0, то ответ верен

    for i in range(n + 1):

        subset[i][0] = True

          

        # Если сумма не равна 0 и набор пуст,

        # тогда ответ неверен

        for i in range(1, sum + 1):

            subset[0][i]= False

              

        # Заполните таблицу подмножеств в нижней части

        for i in range(1, n + 1):

            for j in range(1, sum + 1):

                if j<set[i-1]:

                    subset[i][j] = subset[i-1][j]

                if j>= set[i-1]:

                    subset[i][j] = (subset[i-1][j] or 

                                   subset[i - 1][j-set[i-1]])

      

        # раскомментируйте этот код для печати таблицы

        # для i в диапазоне (n + 1):

        # для j в диапазоне (сумма + 1):

        # print (subset [i] [j], end = "")

        # Распечатать()

    return subset[n][sum]

          
# Программа драйвера для проверки вышеуказанной функции

if __name__=='__main__':

    set = [3, 34, 4, 12, 5, 2]

    sum = 9

    n = len(set)

    if (isSubsetSum(set, n, sum) == True):

        print("Found a subset with given sum")

    else:

        print("No subset with given sum")

          
# Этот код предоставлен
# Сахил Шелангия.

Выход:

Found a subset with given sum

Пожалуйста, ознакомьтесь с полной статьей о проблеме подмножества сумм | DP-25 для более подробной информации!

Рекомендуемые посты:

Программа Python для решения проблемы подмножества сумм | DP-25

0.00 (0%) 0 votes