El problema de la suma de subconjuntos es encontrar un subconjunto de elementos que se seleccionan de un conjunto dado cuya suma suma un número K dado. Estamos considerando que el conjunto contiene valores no negativos. Se supone que el conjunto de entrada es único (no se presentan duplicados).
Algoritmo de búsqueda exhaustiva para la suma de subconjuntos
Una forma de encontrar subconjuntos que suman K es considerar todos los subconjuntos posibles. Un conjunto potencia contiene todos aquellos subconjuntos generados a partir de un conjunto dado. El tamaño de tal conjunto de potencia es 2 N.
Algoritmo de retroceso para la suma de subconjuntos
Usando una búsqueda exhaustiva, consideramos todos los subconjuntos independientemente de si satisfacen las restricciones dadas o no. El retroceso se puede utilizar para hacer una consideración sistemática de los elementos a seleccionar.
Supongamos un conjunto dado de 4 elementos, digamos w[1] … w[4] . Los diagramas de árbol se pueden utilizar para diseñar algoritmos de retroceso. El siguiente diagrama de árbol muestra el enfoque de generación de tupla de tamaño variable.
En el árbol anterior, un Node representa la llamada a la función y una rama representa el elemento candidato. El Node raíz contiene 4 hijos. En otras palabras, root considera cada elemento del conjunto como una rama diferente. Los subárboles del siguiente nivel corresponden a los subconjuntos que incluye el Node principal. Las ramas en cada nivel representan el elemento de tupla a considerar. Por ejemplo, si estamos en el nivel 1, tuple_vector[1] puede tomar cualquier valor de cuatro ramas generadas. Si estamos en el nivel 2 del Node más a la izquierda, tuple_vector[2] puede tomar cualquier valor de las tres ramas generadas, y así sucesivamente…
Por ejemplo, el hijo más a la izquierda de root genera todos esos subconjuntos que incluyen w[1]. De manera similar, el segundo hijo de root genera todos aquellos subconjuntos que incluyen w[2] y excluyen w[1].
A medida que descendemos a lo largo de la profundidad del árbol, agregamos elementos hasta el momento, y si la suma agregada satisface las restricciones explícitas, continuaremos generando más Nodes secundarios. Cuando no se cumplen las restricciones, detenemos la generación de subárboles de ese Node y retrocedemos al Node anterior para explorar los Nodes aún no explorados. En muchos escenarios, ahorra una cantidad considerable de tiempo de procesamiento.
El árbol debería desenstringr una pista para implementar el algoritmo de retroceso (pruébelo usted mismo). Imprime todos aquellos subconjuntos cuya suma suma un número dado. Necesitamos explorar los Nodes a lo largo y ancho del árbol. La generación de Nodes a lo largo de la anchura se controla mediante bucle y los Nodes a lo largo de la profundidad se generan mediante recursividad (recorrido posterior al orden). Pseudo código dado a continuación,
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
A continuación se muestra la implementación de la suma de subconjuntos utilizando un vector de tupla de tamaño variable. Tenga en cuenta que el siguiente programa explora todas las posibilidades similares a la búsqueda exhaustiva. Es para demostrar cómo se puede utilizar el retroceso. Consulte el siguiente código para verificar cómo podemos optimizar la solución de seguimiento.
El poder de retroceder aparece cuando combinamos restricciones explícitas e implícitas, y dejamos de generar Nodes cuando estas comprobaciones fallan. Podemos mejorar el algoritmo anterior fortaleciendo las comprobaciones de restricciones y preclasificando los datos. Al ordenar la array inicial, no necesitamos considerar el resto de la array, una vez que la suma hasta el momento es mayor que el número objetivo. Podemos retroceder y comprobar otras posibilidades.
De manera similar, suponga que la array está preordenada y encontramos un subconjunto. Podemos generar el siguiente Node excluyendo el Node actual solo cuando la inclusión del siguiente Node satisface las restricciones. A continuación se muestra una implementación optimizada (poda el subárbol si no satisface las restricciones).
C++
#include <bits/stdc++.h>
using namespace std;
#define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))
static int total_nodes;
// prints subset found
void printSubset(int A[], int size)
{
for(int i = 0; i < size; i++)
{
cout<<" "<< A[i];
}
cout<<"\n";
}
// qsort compare function
int comparator(const void *pLhs, const void *pRhs)
{
int *lhs = (int *)pLhs;
int *rhs = (int *)pRhs;
return *lhs > *rhs;
}
// inputs
// s - set vector
// t - tuplet vector
// s_size - set size
// t_size - tuplet size so far
// sum - sum so far
// ite - nodes count
// target_sum - sum to be found
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 )
{
// We found sum
printSubset(t, t_size);
// constraint check
if( ite + 1 < s_size && sum - s[ite] + s[ite + 1] <= target_sum )
{
// Exclude previous added item and consider next candidate
subset_sum(s, t, s_size, t_size - 1, sum - s[ite], ite + 1, target_sum);
}
return;
}
else
{
// constraint check
if( ite < s_size && sum + s[ite] <= target_sum )
{
// generate nodes along the breadth
for( int i = ite; i < s_size; i++ )
{
t[t_size] = s[i];
if( sum + s[i] <= target_sum )
{
// consider next level node (along depth)
subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);
}
}
}
}
}
// Wrapper that prints subsets that sum to target_sum
void generateSubsets(int s[], int size, int target_sum)
{
int *tuplet_vector = (int *)malloc(size * sizeof(int));
int total = 0;
// sort the set
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);
}
// Driver code
int main()
{
int weights[] = {15, 22, 14, 26, 32, 9, 16, 8};
int target = 53;
int size = ARRAYSIZE(weights);
generateSubsets(weights, size, target);
cout << "Nodes generated " << total_nodes;
return 0;
}
//This code is contributed by shivanisinghss2110
C
#include <stdio.h>
#include <stdlib.h>
#define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))
static int total_nodes;
// prints subset found
void printSubset(int A[], int size)
{
for(int i = 0; i < size; i++)
{
printf("%*d", 5, A[i]);
}
printf("\n");
}
// qsort compare function
int comparator(const void *pLhs, const void *pRhs)
{
int *lhs = (int *)pLhs;
int *rhs = (int *)pRhs;
return *lhs > *rhs;
}
// inputs
// s - set vector
// t - tuplet vector
// s_size - set size
// t_size - tuplet size so far
// sum - sum so far
// ite - nodes count
// target_sum - sum to be found
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 )
{
// We found sum
printSubset(t, t_size);
// constraint check
if( ite + 1 < s_size && sum - s[ite] + s[ite+1] <= target_sum )
{
// Exclude previous added item and consider next candidate
subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);
}
return;
}
else
{
// constraint check
if( ite < s_size && sum + s[ite] <= target_sum )
{
// generate nodes along the breadth
for( int i = ite; i < s_size; i++ )
{
t[t_size] = s[i];
if( sum + s[i] <= target_sum )
{
// consider next level node (along depth)
subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);
}
}
}
}
}
// Wrapper that prints subsets that sum to target_sum
void generateSubsets(int s[], int size, int target_sum)
{
int *tuplet_vector = (int *)malloc(size * sizeof(int));
int total = 0;
// sort the set
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 %d\n", total_nodes);
return 0;
}
Producción:
8 9 14 22n 8 14 15 16n 15 16 22nNodes generated 68
Como otro enfoque, podemos generar el árbol en tuplas de tamaño fijo análogas al patrón binario. Eliminaremos los subárboles cuando no se satisfagan las restricciones.
– – – Venki .
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA