0-1 zaino: articoli minimi
Problem
Dati N elementi di massa m1, …, mN. Riempiono uno zaino in grado di sopportare un peso non superiore a M. Come aumentare di peso esattamente in M utilizzando il minor numero di articoli possibile?
Inserimento:
- la prima riga contiene un numero naturale N non superiore a 100 e un numero naturale M non superiore a 10000;
- la seconda riga contiene N numeri naturali mi non superiori a 100.
Output: stampa il numero minimo di articoli di cui hai bisogno o 0 se non riesci a raggiungere il peso indicato.
Esempi
| # |
Input |
Uscita |
| 1 |
1 5968
18
|
0 |