Ayuda con problema de backtracking (recursividad) de optimización en C

Iniciado por Albpenu, 24 Septiembre 2021, 19:52 PM

0 Miembros y 1 Visitante están viendo este tema.

Albpenu

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;
           printf("\n %d ",andamio);
       }
   return andamio;
}


Y MUCHÍSIMAS GRACIAS!!! :)

Serapis

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.

fzp

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:

CitarNo 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:

Citarvoid 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?:

Citarif(solucion_parcial == 1)...