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.