En realidad ya tienes una reducción de especial a general. Al establecer , básicamente está utilizando el algoritmo general para resolver el problema especial.s = 0
Por el contrario (es decir, una reducción de general a especial):
Supongamos que está dado un conjunto y un número y hay que determinar si existe algún subconjunto de que resume a .S= { x1, ... , xnorte}KSK
Ahora desea resolver este problema, dado un algoritmo para el caso en el que puede determinar si algún subconjunto suma .0 0
Ahora si , tenemos una reducción fácil: .Xyo> 0S′= { x1, x2, ... , xnorte, - K}
S′ tiene un subconjunto de suma si y sólo si tiene un subconjunto de suma .0 0SK
El problema ocurre cuando podemos tener para algunas de las .Xyo≤ 0yo
Podemos suponer que (¿por qué?).K> 0
Supongamos que la suma de la positiva es y el negativo es . P x i NxiPxiN
Ahora construya un nuevo conjunto tal queS′={y1,y2…,yn}
M = P + | N | + Kyi=xi+M donde .M=P+|N|+K
Cada .yi>0
Ahora ejecute el algoritmo de suma de subconjuntos cero en los conjuntos
S′∪{−(K+M)}
S′∪{−(K+2M)}
S′∪{−(K+3M)}
…
S′∪{−(K+nM)}
Es fácil mostrar que si tiene un subconjunto de suma , entonces al menos uno de los conjuntos anteriores tiene un subconjunto de suma cero.KSK
Te dejaré la prueba de la otra dirección.
La respuesta de Aryabhata se puede solucionar haciendo uso del hecho de que podemos multiplicar todos los números por unac grande , y luego agregar algo pequeño a cada uno para actuar como una "etiqueta de presencia", y luego proporcionar algunos números adicionales que permitirán nosotros llegar a cero si pudiéramos llegar a cK sin ellos. Específicamente, usaremos c=2(n+1) y 1 como la etiqueta de presencia.
Dada una instancia(S={x1,…,xn},K) del problema general con el valor objetivo K , crearemos una instancia del problema específico (con valor objetivo 0) que contenga:
Asumiré como Aryabhatta hace queK es positivo. (Como han pasado 6 años, responderé su ejercicio para el lector: la razón por la que podemos hacer esto es que si intercambiamos los signos de todos los números en una instancia del problema general, incluido K , entonces terminamos con un nueva instancia de problema equivalente. Eso significa que un algoritmo para resolver instancias positivas de K suficiente para resolver cualquier problema: para resolver una instancia con K negativa , podríamos realizar este intercambio de signos, ejecutar ese algoritmo y reenviar su respuesta como la respuesta a la pregunta original y, por supuesto, si K=0 ¡entonces no necesitamos realizar ninguna transformación del caso general en el caso especial!)
Primero, demostremos que una respuesta SÍ a la instancia dada del problema general implica una respuesta SÍ a la instancia construida del problema especial. Aquí podemos asumir que alguna solución{xj1,…,xjm} para el problema general existe: es decir, esta colección no vacía de m números sumas a K . Entonces, si tomamos los valores y correspondientes {yj1,…,yjm} en nuestra solución a la instancia construida, sumarán 2K(n+1)+m . Entonces podemos elegir incluir−2K(n+1)−n en la solución, dejándonos con una suma dem−n . Dado que1≤m≤n , esto está en el rango[−n+1,0] , que podemos extraer con éxito hasta 0 al incluir algún subconjunto de los números desplegables.
Ahora demostremos que una respuesta SÍ a la instancia construida implica una respuesta SÍ a la instancia dada original. Aquí es donde la multiplicación por2(n+1) vuelve importante: es lo que nos permite estar seguros de que los números adicionales que incluimos no pueden "hacer demasiado".
Aquí podemos suponer que existe alguna solución{yj′1,…,yj′m′} para la instancia construida: es decir, esta colección no vacía de números m′ se suma a 0. Según los requisitos del problema, esta solución contiene en menos un elemento Además, debe contener al menos un elemento de Y , ya que sin esto es imposible alcanzar un total de 0: si solo hay números desplegables, entonces la suma está necesariamente en el rango [1,n−1] ( tenga en cuenta que en este caso al menos unoel número desplegable debe estar presente, y todos ellos son estrictamente positivos, por lo que la suma no puede ser 0); mientras que si la solución consiste solo en z y algunos números desplegables, entonces el total es necesariamente negativo porque z=−2K(n+1)−n≤−n lo máximo que los números desplegables pueden aumentar la suma by es n−1 .
y podemos reorganizar los términos:
Esto se puede sustituir directamente de nuevo en la ecuación anterior para obtener
que da una solución a la instancia original del problema general.
fuente