elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Guía actualizada para evitar que un ransomware ataque tu empresa


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Ayuda con problema de backtracking (recursividad) de optimización en C
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Ayuda con problema de backtracking (recursividad) de optimización en C  (Leído 6,512 veces)
Albpenu

Desconectado Desconectado

Mensajes: 3


Ver Perfil
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 :)):
Código
  1. void insertarPiezas(Pieza piezas[])
  2. {
  3.    piezas[0].altura = 5;
  4.    piezas[0].peso = 10;
  5.    piezas[0].coste = 50;
  6.  
  7.    piezas[1].altura = 3;
  8.    piezas[1].peso = 13;
  9.    piezas[1].coste = 70;
  10.  
  11.    piezas[2].altura = 4;
  12.    piezas[2].peso = 28;
  13.    piezas[2].coste = 80;
  14.  
  15.    piezas[3].altura = 7;
  16.    piezas[3].peso = 25;
  17.    piezas[3].coste = 100;
  18.  
  19.    piezas[4].altura = 6;
  20.    piezas[4].peso = 30;
  21.    piezas[4].coste = 90;
  22.  
  23. }
  24.  
  25. ***************ESTA DE DEBAJO ES LA PARTE QUE ME INTERESA Y NO FUNCIONA CORRECTAMENTE EN EL IF...********************
  26.  
  27. void actualizarSolucion(int solucion_parcial[], Pieza piezas[], int andamio[],int *alturaAndamio, int *pesoAndamio, int *costeAndamio, int alturaMin)
  28. {
  29.    int altura_total = 0, peso_total = 0, coste_total = 0;
  30.  
  31.    for(int i = 0; i < NUM_PIEZAS; i++)
  32.    {
  33.        if(solucion_parcial == 1){
  34.            altura_total += piezas.altura;
  35.            peso_total += piezas.peso;
  36.            coste_total += piezas.coste;
  37.        }
  38.    }
  39.  
  40.    if(alturaMin <= altura_total && *costeAndamio <= coste_total){
  41.        printf("\nCoste andamio = %d vs Coste total = %d", *costeAndamio, coste_total);
  42.  
  43.        minimoCoste(solucion_parcial, andamio, altura_total, peso_total, coste_total, *alturaAndamio, *pesoAndamio, *costeAndamio);
  44.  
  45.        *alturaAndamio = altura_total;
  46.        *pesoAndamio = peso_total;
  47.        *costeAndamio = coste_total;
  48.    }
  49. }
  50.  
  51. int minimoCoste(int solucion_parcial[], int andamio[], int altura_total, int peso_total, int coste_total, int *alturaAndamio, int *pesoAndamio, int *costeAndamio)
  52. {
  53.  
  54.        for(int i = 0; i < NUM_PIEZAS; i++)
  55.        {
  56.            andamio = solucion_parcial;
  57.            printf("\n %d ",andamio);
  58.        }
  59.    return andamio;
  60. }

Y MUCHÍSIMAS GRACIAS!!! :)


« Última modificación: 24 Septiembre 2021, 19:54 pm por Albpenu » En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.391


Ver Perfil
Re: Ayuda con problema de backtracking (recursividad) de optimización en C
« Respuesta #1 en: 3 Octubre 2021, 17:27 pm »

Las explicaciones dadas resultan engorrosas, confusas...

Los condicionantes que se exijan no quedan claramente indicadas. Se entiende la generalidad de maximizar el costo, pero, en base a qué?.
Al mínimo número de piezas, al costo de la suma de las piezas que lo componen?. Y en este caso cual es el límite... tu señalas cuantas piezas deben usarse como máximo o deben satisfacer una altura dada y/o no sobrepasar cierto peso, sea cual sea el número de piezas precisas?... si solo estuviera el campo costo de las piezas, sería obvio que se busca el costo mínimo, peor entrnado dos variables más en juego, está uno obligado a entender que tienen repercusión en el cálculo, pero que no defines ni meridianamente.

El código tampoco resulta revelador de estos aspectos, incluso tiene errores, en sendos bucles... hay arrays pero no se ve en parte alguna el uso del índice de los mismos.

En cualquier caso, el bactracking, exige recursividad y/o al menos iteratividad, pero en ningún caso se hace ese tipo de llamadas (ni llamadas recursivas ni llamadas dentro de un bucle) en el código expuesto.
 
Claro que dado el nombre de la función: 'actualizarSolucion', parece ser que ahí simplemente se ofrece salida a una solución temporal (calculada, se supone que óptimizando a un cálculo previo) y que la recursividad para la búsqueda (que quieres solucionar) yazca en otra función pero que aquí no se expone.


En línea

fzp

Desconectado Desconectado

Mensajes: 130


Ver Perfil
Re: Ayuda con problema de backtracking (recursividad) de optimización en C
« Respuesta #2 en: 4 Octubre 2021, 23:07 pm »

Sin tener todo el código es bastante confuso, como ya ha indicado Serapis, las explicaciones son bastante engorrosas. Es difícil entender que significa:

Citar
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.

Por ejemplo NUM_PIEZAS ¿es una variable global accesible desde todas las funciones? En el código que pones aparece en dos funciones actualizarSolucion (línea 31) y minimoCoste (línea 54), pero no aparece definida en ningún sitio.

La definición de la función actualizarSolucion (línea 27) es bastante complicada en cuanto a los argumentos: no se sabe bien qué número de elementos tienen los arreglos... alguno de ellos como piezas [] parece ser de un tipo no básico en C y definido en alguna otra parte del programa (tipo Pieza)...




Pero bueno, por concretar algo, que dices que lo que no funciona es el if (línea 25): si en la línea 27 has definido solucion_parcial como un arreglo que se pasa como argumento a la función actualizarSolucion:

Citar
void actualizarSolucion(int solucion_parcial[], Pieza piezas[], int andamio[],int *alturaAndamio, int *pesoAndamio, int *costeAndamio, int alturaMin)

... ¿Cómo piensas que manejará el programa el if de la línea 33 en la que se trata a solucion_parcial como una variable individual, no cómo un elemento de un arreglo?:

Citar
if(solucion_parcial == 1)...
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Recursividad y Backtracking!!!!
Java
bwsr 2 8,280 Último mensaje 28 Junio 2007, 00:40 am
por bwsr
AYUDA problema de RECURSIVIDAD en C++
Programación C/C++
anapamell 2 2,343 Último mensaje 6 Mayo 2013, 20:04 pm
por anapamell
Ayuda, problema de optimización de memoria
GNU/Linux
JonaLamper 0 4,233 Último mensaje 27 Mayo 2015, 15:57 pm
por JonaLamper
Problema de Backtracking (recursion)
Programación C/C++
KINGARZA 0 2,425 Último mensaje 6 Julio 2017, 08:17 am
por KINGARZA
Problema en ejercicio de backtracking
Programación General
xXJoSe13Xx 0 2,353 Último mensaje 3 Noviembre 2018, 18:15 pm
por xXJoSe13Xx
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines