Páginas: [1] 
|
 |
|
 Autor
|
Tema: alguien tiene el algoritmo de la suma de subconjuntos? (Leído 539 veces)
|
kki
 Desconectado
Mensajes: 76
¡Amo YaBB SE!
|
alguien tiene el algoritmo de la suma de subconjuntos?
que no sea en backtracking ni branch & bound
|
|
|
|
|
En línea
|
|
|
|
|
sirdarckcat
|
Hola, te sirve en dinámica? Primero, explicación de suma de subconjuntos: Tenemos el conjunto: {8,2,3,4,7,8,5,2,1,4,6,9,8,4,1,1,2,5,7,5,2,1,4,7,9,6,3,6,9,8,7,4,6,6,1,6,2,4,5,2,4,2} y buscamos un subconjunto que de suma: 15 El subconjunto: {7,8} da 15 en su suma (entre otros)  ahora, en programación dinámica (en C) el problema queda asi: #include <stdio.h>
#include <stdlib.h>
#define autor "sirdarckcat@gmail.com"
int matriz[502][1002];
int main(int argc, char *argv[]){
int conjunto[502];
int suma;
int i,j,k,a,N=0;
printf("Suma buscada: ");
scanf("%i",&suma);
printf("Numero de Elementos: ");
scanf("%i",&N);
if(N>=500 || N<=0){
printf("Numero invalido, solo de 1 a 499\r\n");
return 1;
}
printf("Elementos separados por espacio: ");
for (i=0;i<N;i++){
scanf("%i",&k);
matriz[0][i]=conjunto[i]=k;
}
for (i=1;i<N;i++){
a=0;
for (j=0;j<N;j++){
matriz[i][j]=(suma>matriz[i-1][j] && matriz[i-1][j]!=-1)?matriz[i-1][j]+conjunto[j+i]:-1;
if (matriz[i][j]==suma && i+j<N){
printf("{");
for (k=0;k<=i;k++){
if(k)printf(",");
printf("%i",conjunto[k+j]);
}
printf("}\r\n");
}
if (matriz[i][j]>suma || matriz[i][j]==-1){
matriz[i][j]=-1;
}else{
a=1;
}
}
if(!a)break;
}
return 0;
}
Ejemplo: Suma buscada: 15
Numero de Elementos: 42
Elementos separados por espacio: 8 2 3 4 7 8 5 2 1 4 6 9 8 4 1 1
2 5 7 5 2 1 4 7 9 6 3 6 9 8 7 4 6 6 1 6 2 4 5 2 4 2
{7,8}
{6,9}
{9,6}
{6,9}
{8,7}
{8,5,2}
{6,3,6}
{1,2,5,7}
{7,5,2,1}
{6,1,6,2}
{4,5,2,4}
Los subconjuntos son los que estan entre llaves. Tambien mando una solucion en excel (las hojas de calculo son muy buenas para programación dinamica) anexa. Deben de contar desde la columna donde esta el numero en rojo, hasta el numero de fila donde esta en la sequencia.. Saludos!! |
|
|
|
|
En línea
|
|
|
|
kki
Desconectado
Mensajes: 76
¡Amo YaBB SE!
|
que grande!! está muy currado tio. ¿no sabrás por casualidad , donde hay uno hecho en divide y venceras?
pd: cuando termine el mio en programacion dinamica lo suelto aqui tambien. , un saludo!
|
|
|
|
|
En línea
|
|
|
|
|
sirdarckcat
|
Este programa se resuelve en O(n^2/2), y aunque en divide&conquer bien implementado deberia terminar en O(nlogn), muchas veces termina en O(n^2) tambien, y lo que pasa en este caso, es que no se como quedaria el algoritmo en divide&conquer.. simplemente no veo como dividirlo, ni como mezclarlo.
es decir.. no me lo imagino, todas las posibles soluciones que me llegan a la mente, terminan siendo muy similares a acotamiento&poda y backtracking.. con una complejidad que supera a la dinámica..
el de dinámica es exponencial.. ¿para que lo quieres asi xD?
en fin..
Saludos!!
|
|
|
|
« Última modificación: 23 Enero 2007, 03:38 por Sirdarckcat »
|
En línea
|
|
|
|
kki
Desconectado
Mensajes: 76
¡Amo YaBB SE!
|
bueno , lo quiero asi porque tengo que entregar una practica de teoria de algoritmos el 31. mmm se podria dividir asi :
dado el conjunto {1,2,3,4} podemos suponer que llegamos a un
caso base cuando quedan 2 elementos o 1. si quedan 2 seria
{1,2} {3,4}
hariamos la suma 1+2=3 y ya no volveríamos a considerar mas esta suma , es decir , antes de ir hacia arriba consideraríamos 1,2 , con 3 y 1,2 con 4 y luego subiriamos... tampoco lo veo muy bien.
lo que no veo para nada es ese algoritmo orden n*log(n) que propones.
voy a seguir dandole vueltas y en cuanto se me ocurra algo lo escribo aqui.
gracias
|
|
|
|
|
En línea
|
|
|
|
|
sirdarckcat
|
El divide esta mal porque que tal que buscas 1,2,3 al dividirlo en 2 ya no lo encontraria.. sacando el divide&conquer de la dinamica (dinamica es un divide and conquer con memoria), la unica forma es: un conjunto de N elementos se dividen en N-1 subconjuntos, y el conquer es cuando la suma es igual a 0.. el programa como ya dije, seria exponencial.. por eso no me convence mucho xD aun asi, tampoco puedes pedir todos los algoritmos, el unico que se necesita es el mas optimo (aunque creo que se podria hacer un poco mas optimo, con O(nlogn) pero lo tengo que pensar bien ).. En fin... suerte! |
|
|
|
|
En línea
|
|
|
|
kki
Desconectado
Mensajes: 76
¡Amo YaBB SE!
|
creo que esta está bien
#include <cstdlib>
#include <cstdio>
// B: suma dada
// lista : lista original de enteros
// n: primer entero de la lista
// sol: solucion , lista de enteros cuya suma es B
// m: numero de elementos de la solucion
int * sumaSubconjuntos(int *list, int n, int *sol, int m, int B) {
printf("SumaSubconjuntos: n=%d m=%d B=%d\n",n,m,B);
int *result;
if (B == 0) return sol;
if (B < 0 || n < 0) return NULL;
if ((result = sumaSubconjuntos(list, n-1, sol, m, B)) != NULL) return result;
sol[m] = list[n];
return sumaSubconjuntos(list, n-1, sol, m+1, B-list[n]);
}
void main(int argc, char **argv) {
int i, *result, B;
int *input = (int *)calloc(1,sizeof(int)*argc);
int *solut = (int *)calloc(1,sizeof(int)*argc);
for (i=2 ; i < argc ; i++) input[i] = atoi(argv[i]);
B = atoi(argv[1]);
result = sumaSubconjuntos(input, argc-2, solut, 0, B);
printf("\n");
for (i=0 ; result[i] != 0 ; i++) printf("%d ",result[i]);
printf("\n");
}
|
|
|
|
|
En línea
|
|
|
|
|
Páginas: [1] 
|
|
|
 |
