Algoritmo

socialux

Nuovo Utente
4 Dic 2005
12
0
0
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.
 

socialux

Nuovo Utente
4 Dic 2005
12
0
0
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??!!).


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!
 

Dusy

Utente Attivo
8 Nov 2005
488
0
0
Germania - Deutschland
Giuro, sarà che ho mal di testa ma non ho capito nulla...
non è che centra con il minimo comune multiplo o
il massimo comun divisore? Solitamente questi algoritmi
si risolvono con modelli matematici...
 

socialux

Nuovo Utente
4 Dic 2005
12
0
0
mi sa che hai mal di testa...perchè penso di avere scritto in maniera più che chiara :D comunque non c'entra nessun minimo comune multiplo...:)
 

Dusy

Utente Attivo
8 Nov 2005
488
0
0
Germania - Deutschland
Scherzavo...comunque ci sto'pensando... :ilpirata:

Solo una domanda: ma A e B devono essere smaltiti del tutto o possono esserci anche
dei residui?
 
Ultima modifica:

socialux

Nuovo Utente
4 Dic 2005
12
0
0
nel testo c'è scritto che la capacità dei contenitori sono sicuramente sufficienti per smaltire tutta l'A e il B prodotti,quindi penso che non possa avanzare nulla...grazie per esserti interessato al mio problema :byebye:
 

Dusy

Utente Attivo
8 Nov 2005
488
0
0
Germania - Deutschland
È solo una cosa divertente...
ma quel che mi turba è... ma se ad esempio alla fine mi rimangono 2 litri di sostanza e incontro un bidone di capacità 10 litri posso versarla o devo aspettare esattamente il contenitore da 2 Litri???

ps. Che scuola vai?
 

socialux

Nuovo Utente
4 Dic 2005
12
0
0
sto diventando scema con questo esercizio...comunque devo cercare la soluzione "ottima" quindi se la soluzione ottima prevede di lasciare due litri fuori...pazienza! comunque frequento un istituto tecnico informatico. ti prego se trovi la soluzione dimmela! :dipser: poi la tradurrò nel linguaccio c.
 

socialux

Nuovo Utente
4 Dic 2005
12
0
0
ok...facciamo che A valga 10 litri e il mio B valga 12 litri, i contenitori (e non bicchieri :) ) facciamo siano 7 con un array contenente le rispettive capacità...[5,3,2,6,3,3,6]...ke ne dici?
 

Dusy

Utente Attivo
8 Nov 2005
488
0
0
Germania - Deutschland
La mia soluzione...ed il mio ragionamento...
la frase: "La sostanza A deve essere distribuita nel MAGGIOR numero possibile di contenitori mentre la B nel MINOR numero di contenitori." corrisponde a dire: A dovrà utilizzare i contenitori più piccoli mentre B i contenitori più grandi...

Per questo motivo dovrò preparare due array nei quali caricherò le capacità dei contenitori ordinate: il primo array in modo descrescente (Array dei contenitori di A) e il secondo crescente (Array dei contenitori di B)...

Array A[2-3-3-3-5-6-6]
Array B[6-6-5-3-3-3-2]

In questo modo:
inconteremo il primo contenitore [5],
capiremo subito se serve ad A o a B...
scorrendo infatti Array A e Array B´, ci rendiamo subito conto che in Array B si incontra prima...
porrò poi il 5 in Array A e Array B a 0 (in modo che non verrà poi ritrovato nelle future ricerche) e riempirò la caraffa con B :beer: e così avanti...

potrebbe funzionare???
 

socialux

Nuovo Utente
4 Dic 2005
12
0
0
sarà che ho mal di testa ma...:D in che senso

incontreremo il primo contenitore [5],
capiremo subito se serve ad A o a B...?

perchè proprio il 5??
 

Dusy

Utente Attivo
8 Nov 2005
488
0
0
Germania - Deutschland
Non il contenitore numero 5 ma il primo contenitore, che contiene visto il tuo esempio il numero 5 ([5,3,2,6,3,3,6]) :D

Nel senso... fai un ciclo che scorre in pari Array A e Array B e con lo stesso indice

ArrayA
ArrayB

appena incontri il valore che stai cercando fermi il ciclo...e vedi se l'hai trovato su ArrayA o
ArrayB.
 
Ultima modifica:

socialux

Nuovo Utente
4 Dic 2005
12
0
0
scusa...sto fondendo mi sa...

comunque facendo come dici te...mettiamo voglio iniziare a smaltire B(facciamo che siano 19 litri e non piu 12 se nò nn viene il problema che voglio porti)...quindi il mio array è

6 6 5 3 3 2

inizio a riempire i primi 2 bidoni e siamo a 12(6+6),poi sommo 5 e siamo a 17 (12+5)..ecco ora se sommo 3 siamo a 20...quindi in questo caso un bidone non sarebbe riempito completamente come invece il problema richiede,a questo punto dovrei scorrere l'array fino al bidone di capacità 2,cosicchè 17 +2 faccia 19 e questa è la soluzione OTTIMA...nel caso nn ci fosse stato il bidone da 2 la soluzione ottima sraebbe stata con l'avanzo di 2 litri. piu o meno hai capito cosa voglio dire??
 

Dusy

Utente Attivo
8 Nov 2005
488
0
0
Germania - Deutschland
Sí ho capito ed era proprio per questo che qualche post fa ti avevo chiesto dell'eventuale avanzo...

mi pare che sto compito sia un po un casino...
me lo porto a casa e ci ragiono un po su!

Buona serata, per ora e vedrai che domani se Dio vuole
avrai la soluizone...magari anche prima di domani e non da me... ;)

Io comunque ci provo zu Hause... :byebye:
bis morgen...
 

socialux

Nuovo Utente
4 Dic 2005
12
0
0
davvero non so come ringraziarti...spero ti ricorderai..comunque io sto un po qui a sclearre ancora un po...ciao e grazie!:byebye:
 

Dusy

Utente Attivo
8 Nov 2005
488
0
0
Germania - Deutschland
Secondo me ciò che rende infine ottima la soluzione è:
visto che B ha bisogno comunque di più contenitori di A,
(La sostanza A deve essere distribuita nel MAGGIOR numero possibile di contenitori mentre la B nel MINOR numero di contenitori)
arrivati alla distribuzione di B nella metà dei contenitori (per difetto es. 7/2=3) o ad esaurimento di B (Ricordiamoci che B deve esaurirsi prima di A). o all'impossibilità di versare B perchè ho contenitori troppo piccoli per B...
so per certo che ciò che rimane apparterrà per definizione ad A e non a B...
scatterà dunque un secondo ciclo che testerà quali dei rimanenti contenitori spettano ancora ad A.

Credo che la soluzione sia all'incirca questa.
Chiederei agli altri partecipanti del forum un parere...:beer:
 
Ultima modifica:

Discussioni simili