|
Mostrar Temas
|
Páginas: [1]
|
1
|
Programación / Programación C/C++ / Ayuda con problema de backtracking (recursividad) de optimización en C
|
en: 24 Septiembre 2021, 19:52 pm
|
Hola compas , por favor, a ver si podéis echarme una manilla sobre cómo abordar correctamente la única condición que me queda en este problema de optimización, en el que se pretende crear un andamio con hasta 5 piezas y minimizando su coste: No logro almacenar en el array con 0 y 1 (andamio[]) la solución correcta de mínimo coste (*costeAndamio < coste_total). He probado con: min 7m, max 8m, y <=25 y me devuelve las piezas 1 y 2, en lugar de la 4, que sería la más barata. Aquí parte del código (el necesario para entender lo que quiero hacer ): void insertarPiezas(Pieza piezas[]) { piezas[0].altura = 5; piezas[0].peso = 10; piezas[0].coste = 50; piezas[1].altura = 3; piezas[1].peso = 13; piezas[1].coste = 70; piezas[2].altura = 4; piezas[2].peso = 28; piezas[2].coste = 80; piezas[3].altura = 7; piezas[3].peso = 25; piezas[3].coste = 100; piezas[4].altura = 6; piezas[4].peso = 30; piezas[4].coste = 90; } ***************ESTA DE DEBAJO ES LA PARTE QUE ME INTERESA Y NO FUNCIONA CORRECTAMENTE EN EL IF...******************** void actualizarSolucion(int solucion_parcial[], Pieza piezas[], int andamio[],int *alturaAndamio, int *pesoAndamio, int *costeAndamio, int alturaMin) { int altura_total = 0, peso_total = 0, coste_total = 0; for(int i = 0; i < NUM_PIEZAS; i++) { if(solucion_parcial == 1){ altura_total += piezas.altura; peso_total += piezas.peso; coste_total += piezas.coste; } } if(alturaMin <= altura_total && *costeAndamio <= coste_total){ printf("\nCoste andamio = %d vs Coste total = %d", *costeAndamio , coste_total ); minimoCoste(solucion_parcial, andamio, altura_total, peso_total, coste_total, *alturaAndamio, *pesoAndamio, *costeAndamio); *alturaAndamio = altura_total; *pesoAndamio = peso_total; *costeAndamio = coste_total; } } int minimoCoste(int solucion_parcial[], int andamio[], int altura_total, int peso_total, int coste_total, int *alturaAndamio, int *pesoAndamio, int *costeAndamio) { for(int i = 0; i < NUM_PIEZAS; i++) { andamio = solucion_parcial; } return andamio; }
Y MUCHÍSIMAS GRACIAS!!!
|
|
|
2
|
Programación / Programación C/C++ / Ayuda con problemas de backtracking, algoritmos de ordenación y búsqueda en C
|
en: 27 Mayo 2021, 19:47 pm
|
Buenas tardes, compas, a ver si alguno me puede echarme un cable con estos ejercicios también: -------------------------------------------------------- ENUNCIADO de Backtracking:
Backtracking. La empresa “Mercanova” desea realizar lotes de alimentos para enviar a empresas. Para cada producto se registra la siguiente información: Nombre del producto Precio del producto (valores entre 2€ y 20€) Marca del producto (Ej: Fuentepesada, Hacendado, Primosol, etc.) Categoría del producto (será una de las siguientes: {Bebidas, Fresco, Postre}) La empresa dispone inicialmente de un stock ilimitado de 16 productos distintos y se desea realizar un programa que confeccione lotes de navidad que contengan 5 productos diferentes, de manera que estos lotes cumplan las siguientes restricciones: El precio de cada lote no puede superar una cantidad indicada por el usuario y debe tener un valor mínimo de 15€ No puede haber más de dos productos de la misma marca en el lote Debe haber al menos un producto de cada categoría en el lote Se pide resolver este problema mediante Backtracking para encontrar la configuración de todos los lotes posibles formados por 5 productos con las restricciones indicadas. Para cada lote solución se debe mostrar por pantalla su composición indicando el nombre, precio, marca y categoría de cada producto incluido. También se debe mostrar el número de nodos generados para obtener la solución. Además, se debe comprobar que la composición de los lotes no se repite, es decir, que no aparezcan dos lotes que tengan los mismos productos pero colocados en distinto orden. El fichero “Mercanova.txt” contiene los 16 productos con la estructura (nombre, precio, marca, categoría) en cada fila del fichero. Nota Importante: El ejercicio debe contener en la memoria los siguientes apartados: Representación y justificación de la solución elegida. Esquema del árbol de búsqueda que se va a generar y total de nodos teóricos que se generarían. Pseudocódigo del esquema solución, explicando las funciones auxiliares utilizadas. Justificar la decisión de decisión de esquema de decisión u optimización.
--------------------------------------------------------- LO QUE LLEVO HECHO del ejercicio de Backtracking: ***EN EL HASHING.H:
#ifndef BACKTRACKING_H_INCLUDED #define BACKTRACKING_H_INCLUDED
typedef struct producto { char nombre; float precio; char marca; char categoria; };
#endif // BACKTRACKING_H_INCLUDED
-------------------------------------------------------- ENUNCIADO de Backtracking:
Backtracking. La empresa “Mercanova” desea realizar lotes de alimentos para enviar a empresas. Para cada producto se registra la siguiente información: Nombre del producto Precio del producto (valores entre 2€ y 20€) Marca del producto (Ej: Fuentepesada, Hacendado, Primosol, etc.) Categoría del producto (será una de las siguientes: {Bebidas, Fresco, Postre}) La empresa dispone inicialmente de un stock ilimitado de 16 productos distintos y se desea realizar un programa que confeccione lotes de navidad que contengan 5 productos diferentes, de manera que estos lotes cumplan las siguientes restricciones: El precio de cada lote no puede superar una cantidad indicada por el usuario y debe tener un valor mínimo de 15€ No puede haber más de dos productos de la misma marca en el lote Debe haber al menos un producto de cada categoría en el lote Se pide resolver este problema mediante Backtracking para encontrar la configuración de todos los lotes posibles formados por 5 productos con las restricciones indicadas. Para cada lote solución se debe mostrar por pantalla su composición indicando el nombre, precio, marca y categoría de cada producto incluido. También se debe mostrar el número de nodos generados para obtener la solución. Además, se debe comprobar que la composición de los lotes no se repite, es decir, que no aparezcan dos lotes que tengan los mismos productos pero colocados en distinto orden. El fichero “Mercanova.txt” contiene los 16 productos con la estructura (nombre, precio, marca, categoría) en cada fila del fichero. Nota Importante: El ejercicio debe contener en la memoria los siguientes apartados: Representación y justificación de la solución elegida. Esquema del árbol de búsqueda que se va a generar y total de nodos teóricos que se generarían. Pseudocódigo del esquema solución, explicando las funciones auxiliares utilizadas. Justificar la decisión de decisión de esquema de decisión u optimización.
--------------------------------------------------------- LO QUE LLEVO HECHO del ejercicio de Backtracking: ***EN EL HASHING.H:
#ifndef BACKTRACKING_H_INCLUDED #define BACKTRACKING_H_INCLUDED
typedef struct producto { char nombre; float precio; char marca; char categoria; };
#endif // BACKTRACKING_H_INCLUDED
***Muchísimas gracias por la ayuda, compas!😊😊😊😊***
|
|
|
3
|
Programación / Programación C/C++ / Ayuda con problema de hashing en C
|
en: 27 Mayo 2021, 19:29 pm
|
Buenas tardes, compas, he estado dándole vueltas a este ejercicio y creo que no sé plantearlo correctamente: -------------------------------------------------------- ENUNCIADO:
Hashing. Se desea implementar un buscador de documentos de manera que al introducir una palabra de búsqueda nos devuelva el nombre de todos los documentos donde aparece esa palabra (no debe devolver el documento completo, sólo el nombre del documento). La implementación debe realizarse usando obligatoriamente una tabla hash y de dos maneras diferentes como se indica a continuación: i. (1,5 puntos) Gestionando las colisiones mediante una técnica de direccionamiento cerrado a elegir por el alumno (lineal, cuadrática o dependiente de clave con recorrido completo). La valoración dependerá de la complejidad de la técnica elegida, siendo lineal y cuadrática menos compleja que la dependiente de clave. ii. (1,5 puntos) Gestionando las colisiones mediante encadenamiento. En este caso se debe además devolver los nombres de los documentos ordenados por relevancia para cada palabra, siendo un documento A más relevante que un documento B para una palabra P si número_palabras(P, A) > número_palabras(P, B), es decir, el número de ocurrencias de P en el documento A es mayor que en el documento B. A continuación se muestra un ejemplo del comportamiento deseado del programa. Suponga que se tienen los tres siguientes documentos D1 D2 D3 Al buscar la palabra “perro”, el programa debe devolver los nombres de documentos “D1” y “D3”. Además, en el apartado b) debe devolver D3 antes que D1 ya que Número_palabras(“perro”, D1) = 1; Número_palabras(“perro”, D3) = 2; por tanto D3 > D1 Se pueden usar los documentos de texto “docA.txt”, “docB.txt” y “docC.txt” adjuntos con este enunciado para probar el programa realizado. Notas importantes: El usuario no puede indicar ni el tamaño de la tabla, ni el campo clave ni ningún otro parámetro de hashing, de eso se debe encargar el programa automáticamente. Se valorará altamente que la tabla hash se cree de manera dinámica y se vaya redimensionando su tamaño según sea necesario o cuando se supere el un factor de carga fijado por el alumno.
--------------------------------------------------------- LO QUE LLEVO HECHO: *** EN EL MAIN.C: #include "hashing.h" #include <stdio.h> #include <stdlib.h> #include <locale.h>
int main(int argc, char *argv[]) { // Codificación en español para la terminal setlocale(LC_ALL, "");
char word[256]; int tam = 0;
printf("Escriba la palabra a buscar: "); scanf("%s",word);
tam = fileWordsCounter("docC.txt"); myreg t_hash[tam]; init(t_hash, tam);// PONE TODA LA TABLA A -1 (FREE) insert(t_hash, tam); search(word, t_hash, tam); //readFile("docA.txt",word);
// if(key == -1) // printf("La palabra a buscar no existe en los documentos"); // else{ // printf("Tabla hash[%d]: ",key); // printfList(hashTable[key]); // }
system("PAUSE"); return EXIT_SUCCESS; }
***EN EL HASHING.C: #include "hashing.h" #include <stdio.h> #include <stdlib.h> #include <string.h>
int fileWordsCounter(char *fileName){ char ch; int words = 0; char word[50];
FILE *fp = fopen(fileName, "r");
if(fp==NULL) { printf("\n ¡No se puede abrir el archivo! \n"); exit(0); } else { while((ch = fgetc(fp)) != EOF && fscanf(fp,"%s",word)) { words++; } }
return words; }
void init(myreg t_hash[], int tam){ int i;
for(i = 0; i < tam; i++){ t_hash.key = 0; t_hash.value = "LIBRE"; } }
void insert(myreg t_hash[], char *fileName, int tam){ int pos;
pos = H(reg.key, tam);
FILE *fp = fopen(fileName, "r");
if(fp==NULL) { printf("\n ¡No se puede abrir el archivo! \n"); exit(0); } else { for(int i = 0; i < tam, i++) { fscanf() } } }
int search(myreg t_hash[], int id, int tam){ int pos;
pos = H(id, tam);
if(t_hash[pos].key == FREE) return -1; //NO EXISTE; PARO DE BUSCAR
if(t_hash[pos].key == id) return pos; else{ printf("Colisión\n"); return -1; //CAMBIAR CONVENIENTEMENTE SEGÚN ESTRATEGIA } }
void readFile(char *fileName, char *word){ char filewords[120]; struct word myreg;
FILE *fp = fopen(fileName, "r");
if(fp==NULL) { printf("\n ¡No se puede abrir el archivo! \n"); exit(0); }
int count = 0; int total = 0; while(fscanf(fp,"%s",filewords) != EOF) { if (strcmp(filewords, word) == 0) { count++; } }
if(count == 0) { printf("\nEl documento '%s' no contiene la palabra '%s'\n",fileName,word); } else if(count == 1) { printf("\nLa palabra '%s' se repite 1 vez en el documento '%s'\n",word,fileName); myreg.key = count; } else { printf("\nLa palabra '%s' se repite %d veces en el documento '%s'\n",word,count,fileName); myreg.key = count; }
printf("\n");
fclose(fp); }
// N/M, donde N es el numero de elemento insertados // M es el tamano de la tabla hash float loadfactor(myreg t_hash[], int tam) { int n_elems = 0; int i;
for(i = 0; i < tam; i++){ if(t_hash.key != LIBRE && t_hash.key != BORRADO) n_elems++; }
return ((float)n_elems/tam); }
void show(myreg t_hash[], int tam){ int i;
for(i = 0; i < tam; i++){ printf("%d | ", t_hash); } printf("\n"); }
***Muchísimas gracias por la ayuda, compas!😊😊😊😊***
- EN HASHING.H puse esto: #ifndef HASHING_H_INCLUDED #define HASHING_H_INCLUDED #define FREE -1 #define DELETED -2
typedef struct word{ char key; char value; } myreg;
int fileWordsCounter(char *fileName); void init(myreg t_hash[], int tam) void insert(myreg t_hash[], myreg reg, int tam); int search(myreg t_hash[], int id, int tam); void show(myreg t_hash[], int tam);
#endif // HASHING_H_INCLUDED
Muchas gracias de nuevo y disculpad mi desconocimiento en esto...😥😥😥
|
|
|
|
|
|
|