0-1 rucksack: das größte gewicht
Problem
Wurde N Goldbarren mit einer Masse von m1, …, mN gegeben. Sie füllen einen Rucksack mit einem Gewicht von M aus. Was ist die größte Menge an Gold, die man in einem solchen Rucksack tragen kann?
Eingabe:
- in der ersten Zeile wird eine natürliche Zahl N eingegeben, die nicht größer als 100 ist, und eine natürliche Zahl M, die nicht größer als 10000 ist;
- In der zweiten Zeile werden N natürliche Zahlen mi eingegeben, die 100 nicht überschreiten.
Impressum: Geben Sie eine ganze Zahl aus - die größte mögliche Menge an Gold, die Sie in diesem Rucksack tragen können.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
2 3195
38 41
|
79 |