Рубрики

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

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

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

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

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");

    }

}

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

Выход:

Found a subset with given sum

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

Джава

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

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");

    }

}

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

Выход:

Found a subset with given sum

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

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

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

0.00 (0%) 0 votes