Proyecto 2 - Subset sum problem

Subset Sum Problem

El problema de la suma de sub conjuntos es una buena introducción para los problemas NP Completos, este es un problema de decisión y no de optimización, y tiene una definición forma muy simple.

Dada el problema puede ser resuelto con una función generadora. Considerando el numero de formas C(m,s) a seleccionar m de M números enteros {a1,….am} tales que su suma es igual a s y se define la función generada como:

Al ampliar “y” esto se convierte

pero como resultado de la ley de exponentes x^m x^n = x^(m+n), Gm(x) es precisamente la función que desee generar:

Por ejemplo:

Dado C un conjunto (15, 22, 14, 26, 32, 9, 16, 8) y s =53. Entonces una solución a G(C,53) está dado por el vector X = (1,1,0,0,0,0,1,0), porque CX = a₁ + a₂ + a₇ = 15 + 22 +16 = 53.El correspondiente del subconjunto es C’ = (15,22,16).

En general ahí puede existir varias soluciones a (C,s) como por ejemplo otra solución es X = (0,1,1,0,0,1,0,1) con el subconjunto C’ = (15,22,16).

El problema de decisión sería:

¿Existe un subconjunto m de M que contenga una suma s?     

Algorithm 1: Exact-Subset-Sum(S, t)

n  <− |S|

L0  <− h0i

Para i = 1 a n hacer:

Li  <− MergeLists (Li−1,Li−1 + xi)

Elimina para Li cada elemento más grande que t

Regresa el elemento más grande para Ln

Algoritmo de tiempo exponencial en general, ya que la duración de Li puede ser tan alta como 2^i.

El problema es NP Completo.


Bibliografía
http://en.wikipedia.org/wiki/Subset_sum_problem
http://www2-fs.informatik.uni-tuebingen.de/~reinhard/krypto/English/4.5.1.e.html
http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/nanda-scribe-3.pdf
http://mathworld.wolfram.com/SubsetSumProblem.html



    A continuación adjunto un archivo con el contenido del reporte con su respectiva codificación en c++.

http://groups.google.com/group/algcomp/web/Proyecto%202%20-%20Subset%20sum%20problem.zip