2votos

Problema de la suma de subconjuntos adaptado [Backtracking] en Haskell

por josejuan hace 6 años

Éste es un problema NP-completo, yo no intentaría hacer un algoritmo eficiente ¡usaría los que gente lista ha hecho! (eg. lpsolve). O bien... >D... usaría un proyector de transparencias http://jose-juan.computer-mind.com/jose-juan/SubSet-Sum-Machine.php

Dado un cojunto de números enteros N cualesquiera buscar un subconjunto de N con cardinalidad mínima que la suma de todos sus enteros sea 0. Restricciones: Si no se encuentra un subcojunto que su suma llegue a 0 se elegirá como solución el subconjunto que sumandose entre sí, dé el número más próximo a 0. En el caso de que para esta solución la cardinalidad del conjunto sea igual, se tomará el número positivo antes que el número negativo.

1
head $ sortBy (\a b -> length a `compare` length b) $ filter (\s -> length s > 0 && 0 == sum s) $ subsequences 
4 comentarios
0votos

Escrito por jmgomez hace 6 años

Muy interesante el artículo de tu Web.
Y lo que has puesto.. Es una solución en Haskell?? Si es así, quiero aprenderlo, pero ya!

Aunque me quedo con las ganas de verlo resuelto usando un árbol de búsqueda :P En fin, ya pondré otro problema (más original) y me aseguraré de que solo pueda ser resuelto así.

Saludos crack!
2votos

Escrito por jneira hace 6 años

Me temo que tu solucion, tal cual, no es pointfree, es decir no es valida sin aplicarlo a un argumento.
Al menos a mi me casca con un

Couldn't match expected type `[[a0]]'
with actual type `[a1] -> [[a1]]'
In the second argument of `($)', namely `subsequences'

Para hacerlo pointfree hay que usar la composicion (.) y no la aplicacion ($) de funciones. Con algun arreglo usando Data.Ord quedaria asi:
minSubsetSum'=head.sortBy(comparing length).filter(\s->s/=[] && sum s==0).subsequences
0votos

Escrito por josejuan hace 6 años

"Me temo que tu solucion"

Efectivamente, es lo que tiene usar ghci y el portapapeles, que en lo que funciona pegas y listo.

+10! (otra vez), muchísimo más elegante, ¡ponla como solución!
0votos

Escrito por jneira hace 6 años

Bueno no es mas que una reelaboracion de tu solucion, que es la que tiene el mondongo.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.