Y al final todo llega y nosotros no hicimos buen papel 🙁 Fuimos un total de 19 grupos a participar y nosotros quedamos en el puesto 11 :'(. De todos modos volveremos el año próximo y venceremos.
De momento decir que me quedé pillado con un problema y analizando la solución era igual que la mia, solo que yo no me di cuenta de una cosa y hacía que el tiempo de ejecución de m algoritmo tendiese a infinito 🙁
La solución del problema es la siguiente. Muchos reconocerán en ella el algoritmo de la mochila o de la estantería. El caso es que yo nunca había oído hablar de él.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include stdlib.h #include stdio.h #define MAX 1001 int T[MAX] = { -1 }; int max(int a, int b) { return a>=b ? a : b; } /** * Pasamos cuanto espacio tenemos y el ultimo libro de la lista a comprobar. * Devuelve el maximo espacio que puede ocupar. */ int A(int espacio, int libros) { int a, b; /* Si el espacio libre es 0 o no hay libros que colocar, el espacio * que ocupamos es 0 */ if( !espacio || !libros) return 0; /* El libro ocupa mas que el espacio que tengo libre, * por lo que sigo sin tenerlo en cuenta */ if( T[libros] > espacio ) return A(espacio, libros-1); /* Si nuestro libro cabe, devolvemos el maximo entre poner * el libro actual e intentarlo con el resto o directamente * intentarlo con el resto sin tener en cuenta el libro * actual */ return max( A(espacio, libros-1), T[libros]+A(espacio-T[libros], libros-1) ); } int main(void) { int i; int espacio; int num_libros; while(1) { scanf("%d %d", &espacio, &num_libros); if( espacio == 0 && num_libros == 0 ) break; for(i = 1; i <= num_libros; i++ ) { scanf("%d", &(T[i])); } printf("%d\n", espacio-A(espacio, num_libros)); } return 0; } |
La solución que yo hice era más como la que sigue:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | #include stdlib.h #include stdio.h #define MAX 1001 int T[MAX] = { -1 }; int max(int a, int b) { return a>=b ? a : b; } /** * Pasamos la lista de libros, el espacio que queda libre y el total de libros en la lista. */ int A(int *tamanos, int espacio, int libros) { int c; int resultado = espacio; int temporal; if( !libros ) return espacio; /* Calculamos el espacio libre teniendo en cuenta que usamos el libro actual */ for(c=1; c < libros; c++) { temporal = A(tamanos[c], espacio-tamanos[0], libros-1); if(temporal<resultado ) resultado = temporal; } /* Calculamos el espacio libre sin tener en cuenta que usamos el libro actual */ for(c=1; c < libros; c++) { temporal = A(tamanos[c], espacio, libros-1); if(temporal < resultado ) resultado = temporal; } return resultado; } int main(void) { int i; int espacio; int num_libros; while(1) { scanf("%d %d", &espacio, &num_libros); if( espacio == 0 && num_libros == 0 ) break; for(i = 1; i <= num_libros; i++ ) { scanf("%d", &a(T[i])); } printf("%d\n", A(espacio, num_libros)); } return 0; } |
Ahora no recuerdo muy bien si era esactamente así, pero sí se que funcionaba. Como podéis comprobar, nuestro gran fallo (bueno, mi gran fallo) fue que pasaba muchas veces por las mismas convinaciones :@ El bucle ese fue mortal y no nos dismo cuenta ninguno que se podía quitar :'(
La próxima vez lo haremos mejor.