Рубрики

Задача суммы подмножеств | DP-25

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

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

Пусть isSubSetSum (int set [], int n, int sum) будет функцией для определения наличия подмножества set [] с суммой, равной sum . n — количество элементов в set [].

Проблема isSubsetSum может быть разделена на две подзадачи
… А) Включить последний элемент, повторить для n = n-1, sum = sum — установить [n-1]
… Б) Исключить последний элемент, повторить для n = n-1.
Если какие-либо из вышеперечисленных подзадач вернут true, тогда верните true.

isSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) || 
                           isSubsetSum(set, n-1, sum-set[n-1])
Base Cases:
isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0 

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

C ++

// Рекурсивное решение задачи о подмножестве сумм
#include <stdio.h>

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

bool isSubsetSum(int set[], int n, int sum)

{

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

   if (sum == 0)

     return true;

   if (n == 0 && sum != 0)

     return false;

  

   // Если последний элемент больше суммы, тогда игнорируем его

   if (set[n-1] > sum)

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

  

   / * иначе, проверьте, можно ли получить сумму любым из следующих

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

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

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

                        isSubsetSum(set, n-1, sum-set[n-1]);

}

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

int main()

{

  int set[] = {3, 34, 4, 12, 5, 2};

  int sum = 9;

  int n = sizeof(set)/sizeof(set[0]);

  if (isSubsetSum(set, n, sum) == true)

     printf("Found a subset with given sum");

  else

     printf("No subset with given sum");

  return 0;

}

Джава

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

class GFG {

      

    // Возвращает true, если есть подмножество

    // of set [] с суммой, равной данной сумме

    static boolean isSubsetSum(int set[],

                            int n, int sum)

    {

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

        if (sum == 0)

            return true;

        if (n == 0 && sum != 0)

            return false;

          

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

        // сумма, затем игнорируем

        if (set[n-1] > sum)

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

          

        / * иначе, проверьте, можно ли получить сумму

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

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

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

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

            isSubsetSum(set, n-1, sum-set[n-1]);

    }

      

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

    public static void main (String args[])

    {

        int set[] = {3, 34, 4, 12, 5, 2};

        int sum = 9;

        int n = set.length;

        if (isSubsetSum(set, n, sum) == true)

            System.out.println("Found a subset"

                          + " with given sum");

        else

            System.out.println("No subset with"

                               + " given sum");

    }

}

  
/ * Этот код предоставлен Раджатом Мишрой * /

python3

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

  
# Возвращает 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")

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

C #

// Рекурсивное решение задачи о подмножестве сумм

using System;

  

class GFG

{

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

    // равно заданной сумме

    static bool isSubsetSum(int []set, int n, int sum)

    {

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

        if (sum == 0)

            return true;

        if (n == 0 && sum != 0)

            return false;

          

        // Если последний элемент больше суммы,

        // тогда игнорируем это

        if (set[n-1] > sum)

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

          

        / * иначе, проверьте, можно ли получить сумму

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

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

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

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

                       isSubsetSum(set, n-1, sum-set[n-1]);

    }

      

    // Драйвер программы

    public static void Main ()

    {

        int []set = {3, 34, 4, 12, 5, 2};

        int sum = 9;

        int n = set.Length;

        if (isSubsetSum(set, n, sum) == true)

            Console.WriteLine("Found a subset with given sum");

        else

            Console.WriteLine("No subset with given sum");

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// Рекурсивное решение задачи о подмножестве сумм

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

function isSubsetSum($set, $n, $sum)

{

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

    if ($sum == 0)

        return true;

    if ($n == 0 && $sum != 0)

        return false;

      

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

    // чем сумма, то игнорируем

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

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

      

    / * иначе, проверьте, может ли сумма быть

       получен любым из следующих

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

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

    return isSubsetSum($set, $n - 1, $sum) || 

        isSubsetSum($set, $n - 1, 

                    $sum - $set[$n - 1]);

}

  
// Код драйвера

$set = array(3, 34, 4, 12, 5, 2);

$sum = 9;

$n = 6;

  

if (isSubsetSum($set, $n, $sum) == true)

    echo"Found a subset with given sum";

else

    echo "No subset with given sum";

      
// Этот код предоставлен Anuj_67
?>

Выход:

Found a subset with given sum

Вышеупомянутое решение может попробовать все подмножества данного набора в худшем случае. Поэтому временная сложность вышеуказанного решения является экспоненциальной. На самом деле проблема является NP-полной (не существует известного решения этой задачи за полиномиальное время).

Мы можем решить эту проблему в псевдополиномиальное время с помощью динамического программирования. Мы создаем подмножество булевой 2D таблицы [] [] и заполняем его снизу вверх. Значение подмножества [i] [j] будет истинным, если существует подмножество множества [0..j-1] с суммой, равной i., В противном случае — ложным. Наконец, мы возвращаем подмножество [sum] [n]

C ++

// Решение для динамического программирования для задачи с суммой подмножеств
#include <stdio.h>

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

bool isSubsetSum(int set[], int n, int sum)

{

    // Значение подмножества [i] [j] будет истинным, если есть

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

    bool subset[n+1][sum+1];

   

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

    for (int i = 0; i <= n; i++)

      subset[i][0] = true;

   

    // Если сумма не равна 0 и набор пуст, тогда ответ ложен

    for (int i = 1; i <= sum; i++)

      subset[0][i] = false;

   

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

     for (int i = 1; i <= n; i++)

     {

       for (int j = 1; j <= sum; j++)

       {

         if(j<set[i-1])

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

         if (j >= set[i-1])

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

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

       }

     }

   

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

     для (int i = 0; i <= n; i ++)

     {

       для (int j = 0; j <= sum; j ++)

          printf ("% 4d", подмножество [i] [j]);

       Е ( "/ п");

     } * /

   

     return subset[n][sum];

}

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

int main()

{

  int set[] = {3, 34, 4, 12, 5, 2};

  int sum = 9;

  int n = sizeof(set)/sizeof(set[0]);

  if (isSubsetSum(set, n, sum) == true)

     printf("Found a subset with given sum");

  else

     printf("No subset with given sum");

  return 0;

}
// Этот код предоставлен Арджуном Тяги.

Джава

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

class GFG {

      

    // Возвращает true, если есть подмножество

    // set [] с солнцем, равным данной сумме

    static boolean isSubsetSum(int set[], 

                             int n, int sum)

    {

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

        // истина, если есть подмножество

        // устанавливаем [0..j-1] с суммой, равной i

        boolean subset[][] = 

                     new boolean[sum+1][n+1];

      

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

        for (int i = 0; i <= n; i++)

            subset[0][i] = true;

      

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

        // тогда ответ ложный

        for (int i = 1; i <= sum; i++)

            subset[i][0] = false;

      

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

        // вверх

        for (int i = 1; i <= sum; i++)

        {

            for (int j = 1; j <= n; j++)

            {

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

                if (i >= set[j-1])

                subset[i][j] = subset[i][j] || 

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

            }

        }

      

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

        для (int i = 0; i <= sum; i ++)

        {

        для (int j = 0; j <= n; j ++)

            System.out.println (subset [i] [j]);

        } * /

      

        return subset[sum][n];

    }

  

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

    public static void main (String args[])

    {

        int set[] = {3, 34, 4, 12, 5, 2};

        int sum = 9;

        int n = set.length;

        if (isSubsetSum(set, n, sum) == true)

            System.out.println("Found a subset"

                          + " with given sum");

        else

            System.out.println("No 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")

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

C #

// Решение для динамического программирования для задачи с суммой подмножеств

using System;

  

class GFG

{

    // Возвращает true, если есть подмножество

    // of set [] с солнцем, равным данной сумме

    static bool isSubsetSum(int []set, int n, int sum)

    {

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

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

        bool [,]subset = new bool[sum+1,n+1];

      

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

        for (int i = 0; i <= n; i++)

        subset[0, i] = true;

      

        // Если сумма не равна 0 и набор пуст, тогда ответ ложен

        for (int i = 1; i <= sum; i++)

        subset[i, 0] = false;

      

        // Заполняем таблицу подмножеств снизу вверх

        for (int i = 1; i <= sum; i++)

        {

            for (int j = 1; j <= n; j++)

            {

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

                if (i >= set[j - 1])

                subset[i, j] = subset[i, j] || 

                               subset[i - set[j - 1], j - 1];

                                              

            }

        }

      

        return subset[sum,n];

    }

      

    // Драйвер программы

    public static void Main ()

    {

        int []set = {3, 34, 4, 12, 5, 2};

        int sum = 9;

        int n = set.Length;

        if (isSubsetSum(set, n, sum) == true)

            Console.WriteLine("Found a subset with given sum");

        else

            Console.WriteLine("No subset with given sum");

    }

}
// Этот код предоставлен Sam007

PHP

<?php
// Решение для динамического программирования
// проблема суммы подмножеств

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

function isSubsetSum( $set, $n, $sum)

{

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

    // быть правдой, если есть подмножество

    // устанавливаем [0..j-1] с суммой, равной i

    $subset = array(array());

  

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

    for ( $i = 0; $i <= $n; $i++)

        $subset[$i][0] = true;

  

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

    // тогда ответ ложный

    for ( $i = 1; $i <= $sum; $i++)

        $subset[0][$i] = false;

  

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

    // вверх

    for ($i = 1; $i <= $n; $i++)

    {

        for ($j = 1; $j <= $sum; $j++)

        {

            if($j < $set[$i-1])

                $subset[$i][$j] = 

                      $subset[$i-1][$j];

            if ($j >= $set[$i-1])

                $subset[$i][$j] = 

                       $subset[$i-1][$j] || 

                       $subset[$i - 1][$j

                               $set[$i-1]];

        }

    }

  

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

    для (int i = 0; i <= n; i ++)

    {

    для (int j = 0; j <= sum; j ++)

        printf ("% 4d", подмножество [i] [j]);

    Е ( "п");

    } * /

  

    return $subset[$n][$sum];

}

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

$set = array(3, 34, 4, 12, 5, 2);

$sum = 9;

$n = count($set);

  

if (isSubsetSum($set, $n, $sum) == true)

    echo "Found a subset with given sum";

else

    echo "No subset with given sum";

  
// Этот код предоставлен anuj_67.
?>

Выход:

Found a subset with given sum

Временная сложность вышеуказанного решения составляет O (сумма * n).

Задача суммы подмножеств в пространстве O (сумма)
Задача идеальной суммы (вывести все подмножества с заданной суммой)

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Задача суммы подмножеств | DP-25

0.00 (0%) 0 votes