Рубрики

C / C ++ Программа для Подмножества Сумм | Откат-4

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

#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;

}

Выход:

10    7   18n   10    5   20n    5   18   12n   20   15n   20nNodes generated 126n

Пожалуйста, ознакомьтесь с полной статьей на Subset Sum | Backtracking-4 для более подробной информации!

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

C / C ++ Программа для Подмножества Сумм | Откат-4

0.00 (0%) 0 votes