Suma de Subconjuntos

[sinalocarlos]

Buen día Foro

No supe donde poner este hilo, espero que aquí sea el lugar correcto.


Desde mis días en la Universidad no me enfrentaba a un problema así:
Tengo una tabla con un identificador y otra columna con valores, el problema es que tengo que, a partir de un valor capturado por el usuario, calcular aquellos identificadores cuya columna valor sume dicha cantidad, la verdad cuando me pidieron eso, al escuchar la explicación tan simple, no pensé que estuviera tan complicado,obviamente pudiera calcular todos los subconjuntos dentro de la tabla pero me da miedo el siquiera calcular el numero de combinaciones posibles.

estuve investigando en Internet al respecto pero al enterarme de que se trata de el clásico ejemplo de un problema NP-Complejo, se me vinieron los ánimos al suelo, así que trate de hacer algún algoritmo que me diera una aproximación a lo que quiero pero hasta ahora no he salido de calcular aquellos subconjuntos que den la suma siempre y cuando estén contiguos.

La pregunta: han tenido experiencia con este problema o con alguna variante? si es así algún consejo?, documentación relacionada? algún truco?

Se agradece cualquier comentario
Gracias por la atención

[Robert01]

No entiendo bien ¿necesitas sumar las veces que un identificador es capturado?

Si no están ordenados es preciso en primer lugar ordenar los identificadores para luego contar los casos.

Si pusieras un ejemplo me quedaría más claro. Si es lo que creo yo hice algo parecido en estos días.

Saludos

[sinalocarlos]

Es cierto no me explique bien

dado el conjunto

Ident Valor
1 [ 4 ]
2 [ 13 ]
3 [ 18 ]
4 [ 25 ]
5 [ 32 ]
6 [ 36 ]
7 [ 51 ]
8 [ 68 ]
9 [ 69 ]
10 [ 76 ]

busco aquellos identificadores cuyo valor es 96 que para este ejemplo serian:
[1,5,7] (no calcule para ver si existen mas) entonces seria sacar todos aquellos subconjuntos en donde la suma de su valor sea dicha cantidad

espero haberme explicado bien esta ves

saludos

[ContraVeneno]

Vamos a ver si entendí...

El usuario quiere saber como se puede sacar el 96, de entre los datos que tienes en la lista.

Según tu, con los elementos 1, 5 y 7, cuyos valores son 4, 32 y 51 sería el resultado esperado... el problema es que esto no me da 96, así que no se si estoy entendiendo bien.

[sinalocarlos]

vaya que no gano para erratas este dia

Tienes razon en lo que dices ContraVeneno, son 2,5,7 cometi un error al anotar 1,5,7

Pero tu supuesto de que es lo que se quiere es el correcto, alguna idea??

Modificando un codigo encontrado en una pagina de la cual les devo el link tengo esta funcion:

Código Delphi [-]

function Tmain_frm.SUMASUB(X:Tarr; k: integer; s:real; r:real; M:real):boolean;
var
        res:boolean;
begin
res:=FALSE;
 if (s = M)  then
 begin
    showmessage('lo encontro');        //        PRINT(A[])
res:=TRUE;
end
 else
 begin

         if (s + X[k].valor <= M)  then
         begin
                X[k].elegido := 1;
                SUMASUB(X,k + 1,s + X[k].valor,r - X[k].valor, M)
         end
         else
         begin
                 X[k].elegido := 0;
                 if ((s + r)>= (X[k].valor )) and ((X[k].valor ) <= (M))  then
                        SUMASUB(X, k + 1, s, r - X[k].valor, M)
         end;
 end;
end;

X: arreglo de registros con los campos elegido, valor y el identificador
k: empieza en 1 y sirve como contador
s: aculado del valor sumado
r: total del valor de los elementos que quedan por revisar
M: valor buscado

Saludos

[[Lepe]]

y digo yo ¿no sería posible cambiar los "Valores".

En programación el 2 elevado a N da mucho juego, con él puedes conseguir fácilmente esos valores que forman la suma.

Ident Valor
1 [ 1 ]
2 [ 2 ]
3 [ 4 ]
4 [ 8 ]
5 [ 16 ]
6 [ 32 ]
7 [ 64 ]
8 [ 128 ]
9 [ 256 ]
10 [ 512 ]

Tampoco intentes buscar otra posible suma para obtener el 96, en este caso usaríamos 6,7

Saludos

[Robert01]

Yo creo que no se pueden cambiar porque no son valores que permanezcan constantes sino las veces que un usuario captura un identificador. Por lo menos eso es lo que le entendí a sinalocarlos.

Estos algoritmos, según estuve viendo, se usan en criptografía.

¿no has visto en algún sitio si hay código optimizado para realizar estas tareas?

Saludos

[sinalocarlos]

[Lepe]
negativo, no se pueden cambiar, en realidad estas columnas son de una tabla mucho mas grande y representan el valor dlls de transacciones unitarias que después en un proceso se agrupan para formar partidas, el problema es que el método por el cual se agruparon lo desconozco, así pues me pidieron que calculara los detalles que cuya suma del valor resultase en cierta cantidad que conocemos (partidas).

y como dices no es necesario para fines prácticos buscar todas las combinaciones posibles con tan solo encontrar una me basta puesto que la posibilidad de que se dupliquen es baja

[Robert01]
negativo, no he podido encontrar código para este problema, existen aproximaciones matemáticas que encuentran soluciones, pero lamentablemente este pobre programador no ha podido aterizarlas a código, como comentas dicho código se usa en criptografía como he podido leer, con el código que anote en el post anterior que me encontré aqui y modifique para delphi se logra encontrar combinaciones siempre y cuando estén contiguas lo cual no ayuda mucho que digamos

seguiré buscando cualquier comentario o sugerencia bienvenida sea

[Robert01]

Aquí hay algunbas cosas interesantes, aunque creo que no es lo que buscas.

[sinalocarlos]

La pagina esta muy bien, la verdad el ingles no se me da muy bien, así que las búsquedas en ese idioma no las hice muy exhaustivas, pero, como veo, se me pasaron paginas interesantes.

Lamentablemente, en la pagina no existe algo que me pueda ayudar, salvo el ejemplo de los subconjuntos, pero el ajustarlo a mis necesidades me tomaría muchísimo tiempo, además de que ataca el problema por fuerza bruta , lo cual es precisamente lo que quiero evitar

muchas gracias por la ayuda, sigo buscando, aunque ya me movieron a otro pendiente aquí en mi trabajo, pero como ya hirió mi amor propio ahora lo termino porque lo termino

Saludos

[[fjcg02]]

Yo te voy a hacer un par de sugerencias suponiendo que lo valores están ordenados ascendentemente:
1.- Acota: es decir, una vez dado el valor, los valores estarán entre el primer valor y el previo menor al valor que buscas.
2.- La minima combinación de sumas, son dos valores. Buscalos.
3.- Si no encuentras la combinación con dos valores, serán tres, y así sucesivamente.


ejemplo según los datos que aportas
Buscamos 29 , con la suma de dos valores
el primer valor será el 1[4], el ultimo el 4[25] ya que es el previo menor.
Sumamos y a la primera.

Buscamos el 45 con dos valores:
el primer valor será el 1[4], el ultimo el 6[36]
Sumamos 4+36, diferente y menor, pasamos a 2[13]+6[36] es mayor,, pasamos a 2[13]+5[32] = 45 OK.
Si seguimos hasta que los valores sean contiguos y o nos quedamos cortos o no llegamos, la combinación pasará por la suma de tres valores.

Buscamos 96
Suponemos que la iteración con dos valores no ha sido satisfactoria.
Pasamos a buscarlo con tres valores.
Primer valor 1[4] y ultimo >10[x]
hacemos todas las combinaciones posibles con el 1 y >10, es decir 1º+2º+x, 1º+3º+x, 1º+4º+x, ... Si no encontramos el valor y terminamos las combinaciones, empezamos lo mismo con el primer valor, y uno menos el mayor. Volvemos a hacer la iteración, bajamos uno el mayor.
Al cabo de un par de iteraciones, ya tendremos el primero 1[4] y el mayor el 7[51], que combinaremos con el 2, 3, 4, 5, 6, y 7. Como no lo encontramos, pasamos a primero 1[4] y el mayor el 7[51], sumamos 4+13+51, 4+18+51, 4+25+51, pasamos a primero 1[4] y el mayor el 6[36], etc. Cuando tengamos hecho todo, pasamos a primero el 2[13] y mayor el 8[68]. Hacemos 13+18+68, y nos hemos pasado. Bajamos el mayor pasamos a primero el 2[13] y mayor el 7[51]. Hacemos 13+18+51 , 13+25+51, 13+32+51 y tararí, encontrado.

Si no encontrasemos una combinación, el resultado sería de 4 sumandos, y así sucesivamente.

ADemás valoraría si a partir de 4 podría usar la función recursivamente, aunque tengo mis dudas.

Bueno, perdona la chapa, espero haberte ayudado y no estar confundido, pensando que es más fácil de lo que realmente es, igual que te pasó a ti en un principio.

Suerte y saludos

[[Lepe]]

Empezado por sinalocarlos

[Lepe]
el problema es que el método por el cual se agruparon lo desconozco,

Ahí está la madre del borrego. Puede que se le añada cierto criterio en la suma para evitar duplicados o vaya a saber lo que el programador pensó.

Si no se sabe con exactitud, es muy posible que pasados 3 meses el programa no encuentre resultados, y entonces, todo el trabajo realizado en esos 3 meses, se deba poner en entredicho.

La verdad, me alegro que te movieran de proyecto .

Saludos