0-1 rucksack: minimale Gegenstände
Problem
Wurde N Objekte mit einer Masse von m1, …, mN gegeben. Sie füllen einen Rucksack mit einem Gewicht von M aus. Wie kann ich genau M mit so wenigen Gegenständen wie möglich an Gewicht zunehmen?
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 die kleinste erforderliche Anzahl an Gegenständen aus, oder 0, wenn Sie dieses Gewicht nicht gewinnen können.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
1 5968
18
|
0 |