PROBLEMIPROBLEMI

2004

Numero minimo di verghe

Carlo, ha un amico che lavora in un negozio di edilizia che spesso si trova a dover soddisfare richieste del tipo:" mi prepari n1 pezzi di verga metallica di lunghezza l1, n2 pezzi di verga di lunghezza l2, ...,nk di lunghezza  lk". Naturalmente questi pezzi vengono tagliati da verghe di lunghezza standard, diciamo L (ad es. 600 cm)  e in generale l1, l2, ...,lk, che sono  minori di L, non sono tutti sottomultipli di L e, qualora alcuni di essi lo siano, il numero di pezzi di lunghezza li ricavabili da una verga (L/li) potrebbe non essere sottomultiplo di ni, come pure il numero di pezzi di lunghezza lj ricavabili da una verga potrebbe non esserlo di nj, e così via .
Il suo problema consiste nel trovare quante verghe occorrono per soddisfare le richieste, in modo da ridurre gli scarti al minimo e quindi, ovviamente,  i costi.

(PUNTEGGIO MASSIMO: 10 PUNTI)