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
#0, tengo curiosidad por ver tu solución, porque las soluciones que se me ocurren a mi no son en general muy prácticas.
#8 es un problema más jodido de lo que parece a simple vista... se me han ocurrido soluciones pero poco elegantes y con un coste enorme, básicamente calculando el precio de todas las combinaciones posibles a piñón
#4 ah, vale, vale, se pueden mezclar baldosas de distinta longitud siempre y cuando cubran la totalidad de la acera, entendido
molan los subs, con cuatro clicks está en portada
#6 nada, propón problemas, que es muy entretenido.
#0 Yo al final he puesto moqueta...
No termino de entender las longitudes que tenemos disponibles o el tema de los precios
o sea simplemente resolver esta ecuación
min((L/ln)*pn)
donde n es la posición en la tabla, ¿no?
cc #1
#2 Yo ya te digo que no acabo de pillarlo, adjunta a #0
#1 Son unidades enteras y en cada problema cambian. En el ejemplo de la entradilla creo que se entiende bien:
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