Partición de número de tiempo pseudopolinomio
En informática , la partición de números de tiempo pseudopolinomiales es un algoritmo de tiempo pseudopolinomial para resolver el problema de la partición .
El problema se puede resolver usando programación dinámica cuando el tamaño del conjunto y el tamaño de la suma de los números enteros en el conjunto no son demasiado grandes para hacer que los requisitos de almacenamiento sean inviables.
Supongamos que la entrada al algoritmo es un conjunto múltiple de cardinalidad :
Sea K la suma de todos los elementos de S. Es decir: K = x 1 + ... + x N . Construiremos un algoritmo que determine si hay un subconjunto de S que suma . Si hay un subconjunto, entonces:
por ejemplo , 1 S = {1, 2, 3, 5}, K = sum(S) = 11, K/2 = 5, encuentre un subconjunto de S que esté más cerca de K/2 -> {2, 3} = 5, 11 - 5 * 2 = 1
ej.2 S = {1, 3, 7}, K = sum(S) = 11, K/2 = 5, encuentre un subconjunto de S que esté más cerca de K/2 -> {1, 3} = 4, 11 - 4 * 2 = 3
