Cómo determinar si un conjunto dado se puede dividir en dos subconjuntos o más de modo que la suma de los elementos en esos subconjuntos sea la misma

Si la suma de los elementos del conjunto es 2n, entonces, para resolver este problema, todo lo que tenemos que hacer es encontrar un subconjunto que diga ‘S1’ del conjunto dado de modo que la suma de elementos en ese subconjunto sea ‘n’. El subconjunto restante (obtenido excluyendo elementos en ‘S1’) se garantiza que tiene suma = ‘n’. Por ejemplo, la suma de todos los elementos para este conjunto {15,5,15,20,45} es 100. Y el subconjunto {5,45} tiene suma = 50. Ahora el subconjunto restante obtenido al excluir los elementos 5 y 45 es {15,15,20} que también tiene suma = 50. Por lo tanto, esto se puede resolver utilizando una estrategia de programación dinámica como se indica en el siguiente enlace:

Establecer problema de partición | Programación dinámica

La idea básica es llenar una tabla 2D llamada solución [] [], donde el valor de la solución [i] [j] es verdadero si la suma de ‘i’ podría obtenerse por cualquier subconjunto del conjunto que tenga los primeros elementos ‘j’ (del conjunto dado) en él. :

Solución recursiva:

Establecer problema de partición | Recursividad

El código y los detalles de implementación se pueden encontrar en los enlaces anteriores.

Espero que esto ayude.

Related Content

¿Cómo podemos encontrar eficientemente la segunda caminata más corta entre dos vértices de un gráfico?

Si todos los códigos de computadora son 0s y 1s, ¿cómo reconoce y entiende la computadora estos símbolos en primer lugar?

¿Existe algún algoritmo simple que pueda resolver la programación del taller?

¿Implementar un algoritmo de detección de esquinas es un buen ejercicio para la visión por computadora?

¿Por qué algunos algoritmos son más eficientes que otros? ¿Por qué se prefiere la búsqueda binaria sobre la lineal?

Lo que está preguntando se llama Establecer problema de partición, que es un problema NP-hard, también conocido como el problema más fácil.

Cuando se saca a los niños de la escuela a jugar fútbol, ​​por ejemplo, se seleccionan dos líderes de equipo de la clase que se turnan para seleccionar a los miembros de su equipo uno por uno. Ambos intentan maximizar la fuerza de sus equipos, terminan tratando de resolver un problema de partición de conjuntos (donde ambos conjuntos tienen un valor igual o más o menos igual) sin saberlo realmente. ¿Puedes adivinar fácilmente qué estrategia siguen?

Algoritmo que implementan sin saber que es lo que se llama un algoritmo codicioso codicioso, simplemente significa que eligen primero la mejor opción. Entonces, si una clase consta de 10 estudiantes con habilidades que varían en una escala del 1 al 10

considere esta matriz que denota las habilidades / fortaleza de esos 10 estudiantes
[4, 2, 5, 8, 7, 6, 3, 2, 2, 1]
los selectores del equipo harían lo siguiente

equipo 1 = {}
equipo 2 = {}

Paso 1
equipo 1 = {8}
equipo 2 = {}

Paso 2
equipo 1 = {8}
equipo 2 = {7}

Paso 3
equipo 1 = {8, 6}
equipo 2 = {7}

Etapa 4
equipo 1 = {8, 6}
equipo 2 = {7, 5}

Paso 6
equipo 1 = {8, 6, 4}
equipo 2 = {7, 5, 3}

Paso 8
equipo 1 = {8, 6, 4, 2}
equipo 2 = {7, 5, 3, 2}

Paso 10
equipo 1 = {8, 6, 4, 2, 2}
equipo 2 = {7, 5, 3, 2, 1}

la suma de habilidades del equipo 1 es 22 y el equipo 2 es 18

lo que deberíamos aprender de esto es que el método codicioso proporciona una buena aproximación pero puede no proporcionar la respuesta correcta que podría ser en este caso

equipo 1 = {2, 8, 6, 3, 1} = 20
equipo 2 = {4, 5, 7, 2, 2} = 20

Entonces, para una respuesta precisa, necesitamos algo más

Una heurística simple podría ser si tiene que dividir el conjunto en 2 conjuntos, la suma del conjunto inicial debe ser divisible por 2 o si tiene que dividir en n número de conjuntos, el resultado total_value del conjunto debe ser divisible por n

Una solución de programación dinámica podría ser encontrar si podemos hacer un subconjunto del conjunto dado que sume a 1 y construir nuestra solución sobre esto
El siguiente es el código de GeeksforGeeks para resolver este problema usando programación dinámica.

// Returns true if arr[] can be partitioned in two subsets of
// equal sum, otherwise false
bool findPartiion (int arr[], int n)
{
int sum = 0;
int i, j; // Caculcate sun of all elements
for (i = 0; i < n; i++)
sum += arr[i]; if (sum%2 != 0)
return false; bool part[sum/2+1][n+1]; // initialize top row as true
for (i = 0; i <= n; i++)
part[0][i] = true; // initialize leftmost column, except part[0][0], as 0
for (i = 1; i <= sum/2; i++)
part[i][0] = false; // Fill the partition table in botton up manner
for (i = 1; i <= sum/2; i++)
{
for (j = 1; j <= n; j++)
{
part[i][j] = part[i][j-1];
if (i >= arr[j-1])
part[i][j] = part[i][j] || part[i - arr[j-1]][j-1];
}
} /* // uncomment this part to print table
for (i = 0; i <= sum/2; i++)
{
for (j = 0; j <= n; j++)
printf ("%4d", part[i][j]);
printf("\n");
} */ return part[sum/2][n];
}

// Returns true if arr[] can be partitioned in two subsets of
// equal sum, otherwise false
bool findPartiion (int arr[], int n)
{
int sum = 0;
int i, j; // Caculcate sun of all elements
for (i = 0; i < n; i++)
sum += arr[i]; if (sum%2 != 0)
return false; bool part[sum/2+1][n+1]; // initialize top row as true
for (i = 0; i <= n; i++)
part[0][i] = true; // initialize leftmost column, except part[0][0], as 0
for (i = 1; i <= sum/2; i++)
part[i][0] = false; // Fill the partition table in botton up manner
for (i = 1; i <= sum/2; i++)
{
for (j = 1; j <= n; j++)
{
part[i][j] = part[i][j-1];
if (i >= arr[j-1])
part[i][j] = part[i][j] || part[i - arr[j-1]][j-1];
}
} /* // uncomment this part to print table
for (i = 0; i <= sum/2; i++)
{
for (j = 0; j <= n; j++)
printf ("%4d", part[i][j]);
printf("\n");
} */ return part[sum/2][n];
}

// Returns true if arr[] can be partitioned in two subsets of
// equal sum, otherwise false
bool findPartiion (int arr[], int n)
{
int sum = 0;
int i, j; // Caculcate sun of all elements
for (i = 0; i < n; i++)
sum += arr[i]; if (sum%2 != 0)
return false; bool part[sum/2+1][n+1]; // initialize top row as true
for (i = 0; i <= n; i++)
part[0][i] = true; // initialize leftmost column, except part[0][0], as 0
for (i = 1; i <= sum/2; i++)
part[i][0] = false; // Fill the partition table in botton up manner
for (i = 1; i <= sum/2; i++)
{
for (j = 1; j <= n; j++)
{
part[i][j] = part[i][j-1];
if (i >= arr[j-1])
part[i][j] = part[i][j] || part[i - arr[j-1]][j-1];
}
} /* // uncomment this part to print table
for (i = 0; i <= sum/2; i++)
{
for (j = 0; j <= n; j++)
printf ("%4d", part[i][j]);
printf("\n");
} */ return part[sum/2][n];
}

// Returns true if arr[] can be partitioned in two subsets of
// equal sum, otherwise false
bool findPartiion (int arr[], int n)
{
int sum = 0;
int i, j; // Caculcate sun of all elements
for (i = 0; i < n; i++)
sum += arr[i]; if (sum%2 != 0)
return false; bool part[sum/2+1][n+1]; // initialize top row as true
for (i = 0; i <= n; i++)
part[0][i] = true; // initialize leftmost column, except part[0][0], as 0
for (i = 1; i <= sum/2; i++)
part[i][0] = false; // Fill the partition table in botton up manner
for (i = 1; i <= sum/2; i++)
{
for (j = 1; j <= n; j++)
{
part[i][j] = part[i][j-1];
if (i >= arr[j-1])
part[i][j] = part[i][j] || part[i - arr[j-1]][j-1];
}
} /* // uncomment this part to print table
for (i = 0; i <= sum/2; i++)
{
for (j = 0; j <= n; j++)
printf ("%4d", part[i][j]);
printf("\n");
} */ return part[sum/2][n];
}

// Returns true if arr[] can be partitioned in two subsets of
// equal sum, otherwise false
bool findPartiion (int arr[], int n)
{
int sum = 0;
int i, j; // Caculcate sun of all elements
for (i = 0; i < n; i++)
sum += arr[i]; if (sum%2 != 0)
return false; bool part[sum/2+1][n+1]; // initialize top row as true
for (i = 0; i <= n; i++)
part[0][i] = true; // initialize leftmost column, except part[0][0], as 0
for (i = 1; i <= sum/2; i++)
part[i][0] = false; // Fill the partition table in botton up manner
for (i = 1; i <= sum/2; i++)
{
for (j = 1; j <= n; j++)
{
part[i][j] = part[i][j-1];
if (i >= arr[j-1])
part[i][j] = part[i][j] || part[i - arr[j-1]][j-1];
}
} /* // uncomment this part to print table
for (i = 0; i <= sum/2; i++)
{
for (j = 0; j <= n; j++)
printf ("%4d", part[i][j]);
printf("\n");
} */ return part[sum/2][n];
}

// Returns true if arr[] can be partitioned in two subsets of
// equal sum, otherwise false
bool findPartiion (int arr[], int n)
{
int sum = 0;
int i, j; // Caculcate sun of all elements
for (i = 0; i < n; i++)
sum += arr[i]; if (sum%2 != 0)
return false; bool part[sum/2+1][n+1]; // initialize top row as true
for (i = 0; i <= n; i++)
part[0][i] = true; // initialize leftmost column, except part[0][0], as 0
for (i = 1; i <= sum/2; i++)
part[i][0] = false; // Fill the partition table in botton up manner
for (i = 1; i <= sum/2; i++)
{
for (j = 1; j <= n; j++)
{
part[i][j] = part[i][j-1];
if (i >= arr[j-1])
part[i][j] = part[i][j] || part[i - arr[j-1]][j-1];
}
} /* // uncomment this part to print table
for (i = 0; i <= sum/2; i++)
{
for (j = 0; j <= n; j++)
printf ("%4d", part[i][j]);
printf("\n");
} */ return part[sum/2][n];
}

// Returns true if arr[] can be partitioned in two subsets of
// equal sum, otherwise false
bool findPartiion (int arr[], int n)
{
int sum = 0;
int i, j; // Caculcate sun of all elements
for (i = 0; i < n; i++)
sum += arr[i]; if (sum%2 != 0)
return false; bool part[sum/2+1][n+1]; // initialize top row as true
for (i = 0; i <= n; i++)
part[0][i] = true; // initialize leftmost column, except part[0][0], as 0
for (i = 1; i <= sum/2; i++)
part[i][0] = false; // Fill the partition table in botton up manner
for (i = 1; i <= sum/2; i++)
{
for (j = 1; j <= n; j++)
{
part[i][j] = part[i][j-1];
if (i >= arr[j-1])
part[i][j] = part[i][j] || part[i - arr[j-1]][j-1];
}
} /* // uncomment this part to print table
for (i = 0; i <= sum/2; i++)
{
for (j = 0; j <= n; j++)
printf ("%4d", part[i][j]);
printf("\n");
} */ return part[sum/2][n];
}

// Returns true if arr[] can be partitioned in two subsets of
// equal sum, otherwise false
bool findPartiion (int arr[], int n)
{
int sum = 0;
int i, j; // Caculcate sun of all elements
for (i = 0; i < n; i++)
sum += arr[i]; if (sum%2 != 0)
return false; bool part[sum/2+1][n+1]; // initialize top row as true
for (i = 0; i <= n; i++)
part[0][i] = true; // initialize leftmost column, except part[0][0], as 0
for (i = 1; i <= sum/2; i++)
part[i][0] = false; // Fill the partition table in botton up manner
for (i = 1; i <= sum/2; i++)
{
for (j = 1; j <= n; j++)
{
part[i][j] = part[i][j-1];
if (i >= arr[j-1])
part[i][j] = part[i][j] || part[i - arr[j-1]][j-1];
}
} /* // uncomment this part to print table
for (i = 0; i <= sum/2; i++)
{
for (j = 0; j <= n; j++)
printf ("%4d", part[i][j]);
printf("\n");
} */ return part[sum/2][n];
}

// Returns true if arr[] can be partitioned in two subsets of
// equal sum, otherwise false
bool findPartiion (int arr[], int n)
{
int sum = 0;
int i, j; // Caculcate sun of all elements
for (i = 0; i < n; i++)
sum += arr[i]; if (sum%2 != 0)
return false; bool part[sum/2+1][n+1]; // initialize top row as true
for (i = 0; i <= n; i++)
part[0][i] = true; // initialize leftmost column, except part[0][0], as 0
for (i = 1; i <= sum/2; i++)
part[i][0] = false; // Fill the partition table in botton up manner
for (i = 1; i <= sum/2; i++)
{
for (j = 1; j <= n; j++)
{
part[i][j] = part[i][j-1];
if (i >= arr[j-1])
part[i][j] = part[i][j] || part[i - arr[j-1]][j-1];
}
} /* // uncomment this part to print table
for (i = 0; i <= sum/2; i++)
{
for (j = 0; j <= n; j++)
printf ("%4d", part[i][j]);
printf("\n");
} */ return part[sum/2][n];
}

También debe leer el problema de Partición en Wikipedia para obtener una explicación.

Vinay Hiwarkar

En primer lugar, la comprobación básica es que si la suma de todos los elementos es impar, nunca se puede dividir en dos conjuntos.

Luego considere que con cada elemento tiene dos opciones:
Ya sea para considerar ese elemento o no

Entonces, si el número de elementos es 4, entonces tiene 16 combinaciones posibles (2 ^ 4).

Por lo tanto, puede preparar una máscara de 0000,0001,0010 … a 1111, cada una indicando si debe considerar el elemento en esa posición o no.
Supongamos que los elementos son {1,5,5,11} y luego la máscara {0,0,0,1} = total_sum / 2

Entonces sabes que {1,5,5} forman un subconjunto y {11} forman el otro subconjunto.

Quizás haya un mejor enfoque, se actualizará cuando tenga uno.

Hiresh Trivedi

Si se va a hacer en Java, use los conceptos de vector, se puede hacer fácilmente ya que puede ordenar, agregar o eliminar elementos y se pueden generar los resultados indicados anteriormente.

PD: agregue más detalles de la pregunta, agregue el código completo que menciona el idioma y su problema, o simplemente indique el objetivo del programa.

Vinay Hiwarkar

puedes seguir esto para mayor claridad

1) Programación dinámica | Conjunto 18 (problema de partición) – GeeksforGeeks
2) dividir un número en dos conjuntos según la suma de dígitos
3) Página en clemson.edu

Espero que esto ayude

Hiresh Trivedi

More Interesting

¿Cómo hacemos que una selección sea estable?

Necesito saber cómo describir el cálculo del PageRank de punto fijo. ¿Alguien sabe algo al respecto?

¿Es la programación una superpotencia? ¿Por qué o por qué no?

¿Cuál es la mejor práctica para el aprendizaje de algoritmos y programación?

¿Cómo se mejora un algoritmo de aprendizaje automático basado en la experiencia?

¿Qué área de finanzas NO se externalizará a computadoras y algoritmos en el futuro?

¿Cuál es el algoritmo más eficiente para descubrir el punto de silla de una matriz?

Paso mucho tiempo pensando en el diseño, por lo que la implementación es terriblemente lenta. ¿Cómo supero este problema?

En el juego de conkers, ¿cómo diseñarías un experimento para identificar qué conkers son mejores?

¿Cuál es el orden cronológico de los algoritmos de reconocimiento facial?

¿Alguien puede ayudarme a resolver el problema SPOJ "Consulta en un árbol" (QTREE)?

¿Cuál es el algoritmo de programación del juego para una temporada regular de la NBA?

He practicado más de 300 preguntas de algoritmos en LintCode y LeetCode. He estado desempleado durante casi 9 meses y obtuve 8 entrevistas y todas fallaron en la prueba de codificación. Todavía no puedo recibir ninguna oferta. ¿Qué tengo que hacer?

¿Cuál es el libro correcto para comprar algoritmos de Amazon y para alguien que no tiene idea sobre el algoritmo?

Para aprender la codificación, ¿primero se debe aprender un lenguaje o algoritmos?