-
[C++]Algoritmo
Salve a tutti,
mi è stato assegnato un programma da fare entro natale,ovviamente a scopo didattico.
Ho 2 sostanze chimiche (A e B) che vanno distribuite in N contenitori (con rispettive capacità) posizionati lungo una strada.La sostanza A deve essere distribuita nel MAGGIOR numero possibile di contenitori mentre la B nel MINOR numero di contenitori.
Le 2 sostanze non possono essere messe nello stesso contenitore.
Ogni volta che si raggiunge un contenitore si può eseguire una delle 3 seguenti opzioni : (1) versare A fino al riempimento del contenitore (2)versare B fino al reimpimento del contenitore (3)non versare nulla.
Input=litri di A e B ; numero N contenitori e rispettive capacità ;
Output=litri di A e B smaltiti nel corrispondente contenitore.
Assunzioni:
- 1 < A,B < 10000
- 1< N < 100
- Le singole capacità dei contenitori sono degli interi positivi di valore inferiore a 10000
- Le capacità dei contenitori sono sicuramente sufficienti per smaltire l'A e il B prodotti.
- I dati di input grantiscono l'esistenza di una (e una sola) souluzione ottima.
- La soulzione ottima prevede che tutti i contenitori utilizzati vengano riempiti completamente (non può succedere che le due sostanze terminino prima che i contenitori effettivamente usati x lo smaltimento siano tutti completamente riempiti).
Ora,ovviamente,non vi chiedo di farmi il programma in C++ ma dato che si avvicina il Natale e siamo tutti più buoni vi sarei molto grata se almeno qualcuno mi aiutasse nell'algoritmo da utilizzare.Poi se qualcuno vuole misurarsi con se stesso e decide di provare a farlo e mi aiuta,che dire,sarebbe fantastico...ciao ciao.
-
ho dimenticato di dire che è da molto poco che uso il linguaggio C e vorrei progredire per gradi....quindi proviamo insieme....molto molto lentamente...
1)effettuo i vari controlli sui dati di input
2)pongo le capacità dei singoli contenitori in un array
3)ordino l'array in senso crescente
4)Mi occupo di smaltire A ricordandomi però delle condizioni :
--versare A fino al riempimento del contenitore o non versare nulla--
ecco partiamo da qua... il problema è cercare di smaltire la sostanza A nel maggior numero di contenitori quindi devo per ora trovare un algoritmo che in pratica inizi a sommare le capacità finchè la somma non superi i litri di A e nel caso la superi andare a cercare nell'array un'altra capacità che mi permetta di smaltire tutta la sostanza (tra l'altro: se non c'è un altro contenitore nell'array che mi permetta di smaltire del tutto la sostanza poichè ogni contenitore deve essere riempito completamente, come famo??!!).
schemino
litri di A: 25
array capacità : 10-5-2-1-7-8-9-17-2-2-5-5
ordiniamo : 1-2-2-2-5-5-5-7-8-9-10-17
utilizzo i bidoni 1-2-2-2-5-5-5-(fino a qui la somma è 22) ora se sommo 7
arrivo a 29 (e nn va bene!),quindi dovrei andare a prendere
un bidone da 7 e togliere uno da 2 e uno da 5 ; questo se
non sbaglio per avere una soluzione "ottima" o sbaglio??
Ok occupiamoci di questo algoritmo per iniziare...che forse per voi sarà una cavolata..ma io ho qualche problema a riguardo!
Permessi di Scrittura
- Tu non puoi inviare nuove discussioni
- Tu non puoi inviare risposte
- Tu non puoi inviare allegati
- Tu non puoi modificare i tuoi messaggi
-
Regole del Forum
Segnalibri