Рубрики

Подмножество Sum | Откат-4

Задача подмножества суммы состоит в том, чтобы найти подмножество элементов, которые выбраны из заданного набора, сумма которого складывается до заданного числа K. Мы рассматриваем множество, содержащее неотрицательные значения. Предполагается, что входной набор является уникальным (дубликаты не представлены).

Алгоритм исчерпывающего поиска для суммы подмножеств

Один способ найти подмножества, которые суммируют с K, состоит в том, чтобы рассмотреть все возможные подмножества. Набор мощности содержит все эти подмножества, сгенерированные из данного набора. Размер такого силового агрегата составляет 2 Н.

Алгоритм возврата для суммы подмножества

Используя исчерпывающий поиск, мы рассматриваем все подмножества независимо от того, удовлетворяют ли они заданным ограничениям или нет. Обратное отслеживание может использоваться для систематического рассмотрения элементов, которые будут выбраны.

Предположим, что данный набор из 4 элементов, скажем, w [1] … w [4] . Древовидные диаграммы могут быть использованы для разработки алгоритмов возврата. Следующая древовидная диаграмма изображает подход генерации кортежа переменного размера.

В приведенном выше дереве узел представляет вызов функции, а ветвь представляет элемент-кандидат. Корневой узел содержит 4 дочерних элемента. Другими словами, root рассматривает каждый элемент множества как отдельную ветвь. Поддеревья следующего уровня соответствуют подмножествам, которые включают родительский узел. Ветви на каждом уровне представляют элемент кортежа, который необходимо рассмотреть. Например, если мы находимся на уровне 1, tuple_vector [1] может принимать любое значение из четырех сгенерированных ветвей. Если мы находимся на уровне 2 самого левого узла, tuple_vector [2] может принимать любое значение из трех сгенерированных ветвей и так далее…

Например, самый левый потомок root генерирует все те подмножества, которые включают w [1]. Точно так же второй потомок корня генерирует все те подмножества, которые включают в себя w [2] и исключают w [1].

По мере того как мы спускаемся по глубине дерева, мы до сих пор добавляем элементы, и если добавленная сумма удовлетворяет явным ограничениям, мы продолжим генерировать дочерние узлы в дальнейшем. Всякий раз, когда ограничения не выполняются, мы прекращаем дальнейшее создание поддеревьев этого узла и возвращаемся к предыдущему узлу, чтобы исследовать еще не исследованные узлы. Во многих случаях это экономит значительное количество времени на обработку.

Дерево должно вызвать подсказку для реализации алгоритма возврата (попробуйте сами). Он печатает все те подмножества, чья сумма складывается до данного числа. Нам нужно исследовать узлы по ширине и глубине дерева. Генерирование узлов по ширине контролируется циклом, а узлы по глубине генерируются с помощью рекурсии (обход после заказа). Псевдокод, приведенный ниже,

if(subset is satisfying the constraint)
    print the subset
    exclude the current element and consider next element
else
    generate the nodes of present level along breadth of tree and
    recur for next levels

Ниже приведена реализация C суммы подмножеств с использованием вектора кортежа переменного размера. Обратите внимание, что следующая программа исследует все возможности, аналогичные исчерпывающему поиску. Это чтобы продемонстрировать, как можно использовать возврат. Смотрите следующий код, чтобы проверить, как мы можем оптимизировать решение по возврату.

#include <stdio.h>
#include <stdlib.h>

  
#define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))

  

static int total_nodes;

// печатает найденное подмножество

void printSubset(int A[], int size)

{

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

    {

        printf("%*d", 5, A[i]);

    }

  

    printf("n");

}

  
// входы
// s - установить вектор
// t - вектор кортежа
// s_size - установить размер
// t_size - размер tuplet до сих пор
// сумма - сумма пока
// ite - количество узлов
// target_sum - сумма, которую нужно найти

void subset_sum(int s[], int t[],

                int s_size, int t_size,

                int sum, int ite,

                int const target_sum)

{

    total_nodes++;

    if( target_sum == sum )

    {

        // Мы нашли подмножество

        printSubset(t, t_size);

        // Исключаем ранее добавленный элемент и рассматриваем следующего кандидата

        subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);

        return;

    }

    else

    {

        // генерируем узлы по ширине

        for( int i = ite; i < s_size; i++ )

        {

            t[t_size] = s[i];

            // рассмотреть узел следующего уровня (по глубине)

            subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);

        }

    }

}

  
// Оболочка для печати подмножеств, которые суммируются с target_sum
// вход - вектор весов и target_sum

void generateSubsets(int s[], int size, int target_sum)

{

    int *tuplet_vector = (int *)malloc(size * sizeof(int));

  

    subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);

  

    free(tuplet_vector);

}

  

int main()

{

    int weights[] = {10, 7, 5, 18, 12, 20, 15};

    int size = ARRAYSIZE(weights);

  

    generateSubsets(weights, size, 35);

    printf("Nodes generated %dn", total_nodes);

    return 0;

}

Сила обратного отслеживания появляется, когда мы объединяем явные и неявные ограничения, и мы прекращаем генерировать узлы, когда эти проверки не пройдены. Мы можем улучшить приведенный выше алгоритм, усилив проверки ограничений и предварительно отсортировав данные. При сортировке исходного массива нам не нужно учитывать оставшуюся часть массива, если сумма пока больше целевого числа. Мы можем вернуться и проверить другие возможности.

Аналогично, предположим, что массив предварительно отсортирован, и мы нашли одно подмножество. Мы можем сгенерировать следующий узел, исключая настоящий узел, только когда включение следующего узла удовлетворяет ограничениям. Ниже приведена оптимизированная реализация (она сокращает поддерево, если оно не удовлетворяет ограничениям).

#include <stdio.h>
#include <stdlib.h>

  
#define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))

  

static int total_nodes;

  
// печатает найденное подмножество

void printSubset(int A[], int size)

{

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

    {

        printf("%*d", 5, A[i]);

    }

  

    printf("n");

}

  
// функция сравнения qsort

int comparator(const void *pLhs, const void *pRhs)

{

    int *lhs = (int *)pLhs;

    int *rhs = (int *)pRhs;

  

    return *lhs > *rhs;

}

  
// входы
// s - установить вектор
// t - вектор кортежа
// s_size - установить размер
// t_size - размер tuplet до сих пор
// сумма - сумма пока
// ite - количество узлов
// target_sum - сумма, которую нужно найти

void subset_sum(int s[], int t[],

                int s_size, int t_size,

                int sum, int ite,

                int const target_sum)

{

    total_nodes++;

  

    if( target_sum == sum )

    {

        // Мы нашли сумму

        printSubset(t, t_size);

  

        // проверка ограничений

        if( ite + 1 < s_size && sum - s[ite] + s[ite+1] <= target_sum )

        {

            // Исключить предыдущий добавленный элемент и рассмотреть следующего кандидата

            subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);

        }

        return;

    }

    else

    {

        // проверка ограничений

        if( ite < s_size && sum + s[ite] <= target_sum )

        {

            // генерируем узлы по ширине

            for( int i = ite; i < s_size; i++ )

            {

                t[t_size] = s[i];

  

                if( sum + s[i] <= target_sum )

                {

                    // рассмотреть узел следующего уровня (по глубине)

                    subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);

                }

            }

        }

    }

}

  
// Обёртка, которая печатает подмножества с суммой в target_sum

void generateSubsets(int s[], int size, int target_sum)

{

    int *tuplet_vector = (int *)malloc(size * sizeof(int));

  

    int total = 0;

  

    // сортируем множество

    qsort(s, size, sizeof(int), &comparator);

  

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

    {

        total += s[i];

    }

  

    if( s[0] <= target_sum && total >= target_sum )

    {

  

        subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);

  

    }

  

    free(tuplet_vector);

}

  

int main()

{

    int weights[] = {15, 22, 14, 26, 32, 9, 16, 8};

    int target = 53;

  

    int size = ARRAYSIZE(weights);

  

    generateSubsets(weights, size, target);

  

    printf("Nodes generated %dn", total_nodes);

  

    return 0;

}

В качестве другого подхода мы можем генерировать дерево в виде кортежей фиксированного размера, аналогичных двоичному шаблону. Мы убьем поддеревья, когда ограничения не будут выполнены.

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

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

Подмножество Sum | Откат-4

0.00 (0%) 0 votes