¿Subset Sum permite multisets?

En el problema de la suma de subconjuntos, ¿pueden ser iguales algunos de los números dados ? Por ejemplo, podríamos tener y el objetivo es ? ¿Puedo suponer que tengo una solución específica con los números y y y no? $a_1,a_2,a_3,\dots,a_n$ $[1,1,1,2,3,4]$ $5$ $2$ $3$ $1,1,1$ $2$

complexity-theory terminology curioso
fuente

Tú dices potayto, yo digo potahto. Es bastante común que los informáticos difuminen la distinción formal entre conjuntos y conjuntos múltiples; la única manera de estar seguro es leer la definición cuidadosamente . Todas las variantes del problema Subset Sum son NP-complete.

JeffE

Respuestas:

Una pregunta que podríamos hacer es "¿Podemos reducir esto al problema de la suma de subconjuntos?" En este caso, la respuesta es sí : para cada duplicado lo reemplazamos con dos números e tal que . $z$ $x$ $y$ $x+y=z$

[- 1, - 1, 2, 3] \to [- 7, - 1, 2, 3, 6]

$[-1,-1,2,3]\to [-7,-1,2,3,6]$

Sin embargo, debemos tener cuidado de no introducir soluciones adicionales (aquellas que usan solo sin ), lo que podemos hacer haciendo para , y para . Específicamente, esto impide el uso de sin (y viceversa) al hacer la suma de todos los números negativos estrictamente por encima de cero (y por lo tanto no satisface el problema tradicional de la suma de subconjuntos). $x$ $y$ $x>\lvert \Sigma(a_i)\rvert$ $a_i<0\in A$ $y<-\lvert\Sigma(a_i)\rvert$ $a_i>0 \in A$ $x$ $y$ $x$

Merbs
fuente