Рубрики

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

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

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

// Рекурсивное решение задачи о подмножестве сумм
#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;

}

Выход:

Found a subset with given sum

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

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;

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

Выход:

Found a subset with given sum

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

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

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

0.00 (0%) 0 votes