Salve a tutti. Avrei bisogno di una mano con un programma che dovrei impelemtare in java con la tecnica dell'algoritmo greedy. il testo del problema è il seguente: Un collezionista decide di organizzare al meglio la sua collezione di minerali, composta in totale
da M pezzi diversi. Ogni minerale m ha un peso indicato da un numero reale pm, e il collezionista
ha a disposizione S scatole, con S >= M, con ogni scatola s che puó contenere un unico oggetto di
peso totale indicato con un numero reale <= cs.
Si chiede di progettare un algoritmo che assegni ad ogni oggetto una scatola diversa, facendo
in modo che alla fine degli assegnamenti il peso "sprecato" sia minimo.
Vi viene fornito un file strutturato come segue
3 2
c_1
c_2
c_3
p_1
p_2
Ovvero nella prima riga sono presenti il numero di scatole e il numero totale di minerali. Nelle
seguenti S righe sono presenti i valori del peso massimo che ogni scatola puó contenere, e a seguire
ci sono i pesi degli M minerali.
Ogni scatola ha un identificativo implicito dato dal suo numero di riga, partendo da 1. Ogni
oggetto ha un identificativo implicito dato dal numero di riga, partendo da 1. Nell’esempio precedente
ci sono quindi 3 scatole di identificativi 1,2,3, con massimo peso c1, c2, c3, e 2 minerali di
identificativi 1,2 con peso p1 e p2.
L’algoritmo deve produrre in output l’elenco delle scatole da utilizzare seguito dall’identificativo
dell’oggetto. Nell’esempio precedente, qualora l’algoritmo decidesse di mettere l’oggetto di identificativo
1 nella scatola con identificativo 2, e l’oggetto di identificativo 2 nella scatola di identificativo
3, l’output da presentare sarebbe il seguente:
2 1
3 2
Grazie per la collaborazione