Buste

Innanzitutto, per semplificare le cose, conviene dividere tutti i valori per 5: quindi avremo banconote da 1, 2, 4, 10, 20, 40, 100 per un totale di 1000.
La prima idea è di mettere nelle buste 1, 2, 4, 8, ..., 256, 512. In questo modo arriveremo a 1000, anzi a 1024, semplicemente scrivendo in codice binario il numero e selezionando la busta corrispondente. Si può fare di meglio? Sì.
La soluzione che ho trovato io usa questi valori (già ricalcolati per i valori originali:

5 (5)
10 (10)
20 (20)
40 (20, 20)
80 (50, 20, 10)
160 (100, 50, 10)
320 (200, 100, 20)
625 (500, 100, 20, 5)
1250 (500, 500, 200, 50)
2500 (500, 500, 500, 500, 500)

per un totale di 27 banconote. L'ottava busta può anche contenere 630 euro (500, 100, 20, 10) oppure 640 euro (500, 100, 20, 20) per un totale di tre soluzioni essenzialmente distinte.

Un'ultima parola

Non è detto che questa sia la soluzione migliore in assoluto, o almeno io non sono riuscito a dimostrarlo.