Greedy-Algorithmen
Greedy-Algorithmen sind eine beliebte Reihe von Herangehensweisen, bei denen die finale Lösung Schritt für Schritt aufgebaut wird und in jeder Phase stets die offensichtlichste bzw. optimalste Entscheidung getroffen wird. In der Regel sind sie recht leicht nachvollziehbar, doch manchmal kann es knifflig sein, die passende Heuristik für jeden Schritt zu finden.
Herausforderung
Du hast einen Rucksack und
n Gegenstände. Du möchtest so viele Gegenstände wie möglich verstauen, weißt jedoch, dass der Rucksack reißen kann, falls das Gesamtgewicht den Grenzwert t überschreitet. Du möchtest wissen, wie viele Gegenstände du maximal mitnehmen kannst, ohne dass dieser beschädigt wird.Eingabe
Die erste Zeile der Eingabe enthält zwei Ganzzahlen
n (1 ≤ n ≤ ) und t (1 ≤ t ≤ ) – die Anzahl der Gegenstände und den maximalen Grenzwert, den der Rucksack tragen kann.Die nächste Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ ) – das Gewicht jedes einzelnen Gegenstands.Ausgabe
Das Programm soll die maximale Anzahl an Gegenständen ausgeben, die du mitnehmen kannst.
Beispiele
Input | Output |
7 10
4 1 2 5 8 7 1 | 4 |
Erläuterung
Wir können zum Beispiel
1, 2, 5, 1 oder 4, 1, 2, 1 oder 1, 2, 7, 1 mitnehmen. In jedem dieser Fälle sind es insgesamt 4 Gegenstände.Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB