algorithm - sacar - ¿Es esta variante del problema de la suma de subconjuntos más fácil de resolver?

problemas np ejemplos

Question

Tengo un problema relacionado con el problema de suma de subconjuntos y me pregunto si las diferencias lo hacen más fácil, es decir, que se puede resolver en un tiempo razonable.

Dado un valor V, un tamaño de conjunto L, y una secuencia de números [1, N] S, ¿cuántos subconjuntos de tamaño L de S suman menos que V?

Esto es diferente al problema de suma de subconjuntos de tres maneras:

1. Me importa cuántos subconjuntos son menores que un valor dado, no cuántos son iguales .
2. Los tamaños del subconjunto son fijos.
3. Me importa cuántos conjuntos suman menos que V, no solo si existe alguno.

¿Hay algún algoritmo razonablemente eficiente para resolver esto?

Editar: Obviamente, esto se puede hacer en O (N elegir L) usando un algoritmo de generación de combinación. Lo que realmente me interesa son los trucos inteligentes para acelerarlo significativamente más allá de eso.

Answer 1

¿No es solo el problema de Knapsack con un giro? Sin embargo, podría estar equivocado.

Answer 2

(La versión de decisión de) su problema todavía es NP-completo. La idea es que si pudiéramos resolver su problema, entonces (para cada tamaño de subconjunto, por ejemplo) podríamos preguntar cuántos conjuntos suman menos de V y cuántos suman menos de V-1, y la diferencia de esos dos números sería díganos si son subconjuntos que suman exactamente V, por lo que podríamos resolver el problema de la suma de subconjuntos. [Esta no es una prueba completa, porque es una reducción de Turing , no una reducción de muchos .]

Sin embargo, hay una solución de programación dinámica simple que se ejecuta en tiempo O (nLV). [La razón por la que esto no prueba que P = NP es que V podría ser exponencial en el tamaño de entrada: con n bits, puede representar valores hasta 2 ⁿ . Pero suponiendo que tu V no es exponencial, esto no es un problema.]

Deje num [v] [k] [i] denotar el número de subconjuntos de tamaño k de los primeros i elementos de S que suman v. Puede calcularlos como (para cada i):

    num[0][0][i] = 1
    for v = 1 to V:
        for k = 1 to L:
            num[v][k][i] = num[v][k][i-1] + num[v-S[i]][k-1][i-1]

donde S [i] es el elemento ith en tu secuencia. (Cualquier conjunto de tamaño k que suma v no usa S [i], por lo que se cuenta en num [v] [k] [i-1], o usa S [i], lo que significa que el resto de el subconjunto tiene elementos k-1, usa solo los primeros números i-1 en la secuencia y sumas para vS [i].) Finalmente, cuente num [v] [L] [| S |] por cada v menor que V ; esa es tu respuesta.

Además, puede omitir el tercer subíndice si lo hace con cuidado (ejecute el ciclo hacia abajo para cada i, etc.); Solo lo incluí para mayor claridad.

Answer 3

Bueno, para empezar, ya que estás especificando size = L, incluso si no puedes pensar en algo inteligente y solo usas la fuerza bruta, tendrás (N eliges L) sumas separadas en el peor de los casos, por lo que es un poco mejor que n ^^ L (bueno, L + 1, ya que entonces sumaría cada subconjunto).

Answer 4

Esto suena como una n elección de la categoría k del problema. Generar k-subconjuntos de n está cubierto en el Manual de diseño de algoritmos de Skiena, y el libro sugiere enumerar subconjuntos relevantes en orden lexicográfico (recursivamente, por ejemplo). Luego haga su suma y comparación en cada subconjunto.

Si tiene un conjunto ordenado, es probable que pueda eliminar soluciones imposibles del espacio de solución.

Answer 5

No estoy preparado para presentar una prueba, pero parece que podría ser susceptible a un esquema de programación dinámico: tabular la lista de subconjuntos de tamaño 2utilizarlos en subconjuntos de computadora de tamaño 3, etc., de modo que hyou solo necesita examinar un pequeña colección de prospectos.

Answer 6

Una optimización que viene a la mente es esta: ordena tu secuencia (si no es así). Elija los primeros elementos L-1 desde el principio, y luego elija el último elemento tal que sea el valor más grande posible (el siguiente valor más grande en la secuencia daría una suma demasiado grande). Deseche el resto de la secuencia, porque esos elementos nunca pueden ser parte de un subconjunto válido de todos modos.

Después de eso, supongo que es una búsqueda completa de nuevo. Pero también podría haber otras optimizaciones posibles.

Answer 7

La solución de programación dinámica al problema de suma de subconjuntos genera una tabla que contiene esta respuesta (es decir, una tabla booleana de V por N donde V es el número máximo de elementos y N es el número máximo de elementos que pueden estar en un conjunto que satisface restricciones, cada booleano es verdadero si <= N elementos suman a <= V). Entonces, si N * V no es demasiado grande para usted, existe un algoritmo aceptablemente rápido. La solución de suma de subconjuntos es simplemente el elemento más alto en esta tabla para el cual la cantidad de elementos es <= N / 2.

Answer 8

Si solo son enteros positivos, puede hacer un paso de verificación si lo necesita ;

Tome la suma de los enteros L-1 más pequeños en el conjunto. Si es una suma X, entonces nX debe estar debajo del elemento más grande si se supone que el problema tiene una solución. Ahora que lo pienso, puedes eliminar a otros L de esta manera ...

Answer 9

Quizás la formulación de programación dinámica sea amenazante para un PTAS de FPTAS.