7 meneos
134 clics
Baldosas a bajo coste
Se considera una acera de longitud L y anchura 1, que se quiere recubrir completa con baldosas con distintas longitudes (todas tienen anchura 1) y de distintos precios. Se dispone de b baldosas, de longitudes (l1,l2,...,lb) y precios (p1,p2,...,pb). Se pretende recubrir la acera con baldosas con el menor coste posible. Por ejemplo, si L=5, l=(4,1,3,2,1) y p=(3,2,1,4,1) la solución óptima es de precio 4, y se obtiene con las baldosas 1 y 5, de longitudes 4 y 1 y precios 3 y 1, o con las 2, 3 y 5, de longitudes 1, 3 y 1 y precios 2, 1 y 1.
|
comentarios cerrados
No termino de entender las longitudes que tenemos disponibles o el tema de los precios
min((L/ln)*pn)
donde n es la posición en la tabla, ¿no?
cc #1
Por ejemplo, si L=5, l=(4,1,3,2,1) y p=(3,2,1,4,1) la solución óptima es de precio 4, y se obtiene con las baldosas 1 y 5, de longitudes 4 y 1 y precios 3 y 1, o con las 2, 3 y 5, de longitudes 1, 3 y 1 y precios 2, 1 y 1.
Tú tienes una acera de longitud 5. Y baldosas cada una de longitudes 4, 1, 3, 2 y 1. Y cada precio de cada baldosa es de 3, 2, 1, 4 y 1 respectivamente. En ese caso la solución óptima es de precio 4, eligiendo las baldosas 1 y 5 (de longitud 4 y 1 (4+1=5), y precios 3 y 1 respectivamente (3+1=4)), con lo que consigues llenar la acera, que era de longitud 5, con un precio mínimo. Ahora bien, la solución óptima no es única para ese caso, y también podría conseguirse eligiendo las baldosas 2, 3 y 5 (de longitudes 1, 3 y 1 (1+3+1=5) y precios 2, 1 y 1 (2+1+1 = 4) respectivamente).
Las longitudes que "tenemos disponibles" no están concretadas, a veces L será 5, otras 10, otras 15, y a veces tendremos 6 baldosas, o 7, cada caso cambia: se debe resolver para todos los casos posibles. Por eso, sí, hay que minimizar coste, pero maximizando longitud cubierta en la acera. Se puede formalizar la solución con recurrencia.
cc #2