Рубрики

Программа на C # для задачи с подмножеством сумм | DP-25

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

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

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

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

Выход:

Found a 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

Выход:

Found a subset with given sum

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

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

Программа на C # для задачи с подмножеством сумм | DP-25

0.00 (0%) 0 votes