Algoritmi Greedy
Gli algoritmi greedy costituiscono un popolare insieme di strategie che costruiscono la soluzione finale passo dopo passo, scegliendo sempre la soluzione apparentemente più ovvia o ottimale a ogni fase. In genere sono abbastanza semplici da implementare, ma talvolta può risultare complicato individuare l’euristica corretta per ogni passaggio.
Sfida
Hai uno zaino (knapsack) e
n oggetti. Vuoi inserire quanti più oggetti possibile, ma sai che lo zaino si strapperà se il contenuto è troppo pesante (ossia, se la somma dei pesi supera la soglia t). L’obiettivo è determinare il numero massimo di oggetti che puoi mettere al suo interno senza danneggiarlo.Input
La prima riga dell’input contiene due interi
n (1 ≤ n ≤ ) e t (1 ≤ t ≤ ): rispettivamente, il numero di oggetti e il limite di peso supportato dallo zaino.La riga successiva contiene
n interi separati da spazio, (1 ≤ ≤ ), che rappresentano i pesi di ciascun oggetto.Output
Il programma deve stampare il numero massimo di oggetti che è possibile trasportare.
Esempi
Ingresso | Uscita |
7 10
4 1 2 5 8 7 1 | 4 |
Spiegazione
Possiamo trasportare
1, 2, 5, 1, oppure 4, 1, 2, 1, oppure ancora 1, 2, 7, 1. In tutti i casi si tratta di 4 oggetti in totale.Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB