[C++] Algoritmo

[socialux]

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.

[ibykos]

Ciao!
E' un problema interessante, allora: per prima cosa un po' di considerazioni

Il problema sembra impostato in modo tale da richiedere una soluzione con ricorsione + backtracking

Sembrano anche esserci alcune soluzioni greedy, mentre l'ottimo è un po' più complicato.

Ricerca dell'ottimo:

Una funzione riempie ricorsivamente i contenitori con il liquido A a partire dai più piccoli (strategia greedy) e cerca, mediante backtracking, tutte le soluzioni, che memorizza e salva da qualche parte.
Un'altra funzione (oppure la stessa) riempie i contenitori con il liquido B a partire dai più grossi con il backtracking e di nuovo salva tutte le soluzioni da qualche parte.
Un'ultima funzione accoppia le soluzioni di A con quelle di B e valuta

1- se sono compatibili, cioè se non usano gli stessi contenitori e se, messe assieme, le due soluzioni che costituiranno la soluzione finale non violano qualche clausola del problema

2- il parametro di ottimo: il parametro di ottimo secondo me è la differenza tra quanti contenitori ho riempito con A (il più alto possibile) e quanti contenitori ho riempito con B 8il più basso possibile), più è alta è la differenza e migliore è la soluzione.

Alla fine scegli la soluzione con il valore di ottimo più alto

Questo problema mi interessa molto (io sono una amante degli algoritmi) e mi piacerebbe che mi tenessi informato sugli sviluppi.

Buona fortuna!

[socialux]

ehm...ok..questo era in russo,ora in italiano? sto scherzando ovviamente! la colpa è mia poichè 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!

[ibykos]

Ho usato delle parole strane perché l'esercizio che hai proposto sembra il compito di un qualche esame di "algoritmi e programmazione" di una qualche facoltà di informatica.
Esistono dei metodi standardizzati er risolvere questo tipo di problemi, ed usarene altri potrebbe rendere la soluzione molto difficile.

Prima di tutto definisco i termini tecnici che ho usato

Ricorsione: Effetto di una chiamata a funzione ricorsiva.
Una funzione ricorsiva è unafunzione che chiama se stessa in maniera tale da trasformare un grosso problema in tanti problemi più piccoli della stessa natura, per esempio, fattoriale (x) = x*fattoriale(x-1).

Backtracking: Quando un problema viene trattato per mezzo di ricorsione, si costruiscono delle soluzioni pezo per pezzo, montanto un nuovo pezzo su quello precedente fino a quando si riesce.
Quando non si è più in grado di proseguire si smonta un pezzo, per poi provare a montarne altri (se ce ne sono) oppure si smonta un altro pezzo ancora (se non ci sono altri pezzi da provare dopo).
La "retromarcia" è detta backtracking ed è il procedimento mediante il quale si esplorano tutte le soluzioni provando ogni possibile combinazioni dei dati in ingresso.

Strategia greedy: Un metodo intelligente che permette di evitare di esplorare tutte le combinazioni ma che garantisce di trovare un risultato abbastanza buono, però non è detto che trovi l'ottimo.

Parametro di ottimo: formalizzazione del criterio di valutazione di un risultato.

Troppa teoria ora guardiamo una possibile base di dati.

1) un vettore di contenitori

Potremmo usare un vettore di interi, ma è più chiaro chiamare le cose con il proprio nome.
I campi del contentore potrebbero essere

typedef struct {int ID ; int capacità ; bool usato; } contenitore;

2)Poi ci servono un paio di interi per i due liquidi magari ridefinendo int come LIQUIDO .

3)Ci serve anche un tipo in grado di immagazzinare una soluzione

soluzione deve contenere un vettore variabile di interi e magari il suo parametro di ottimo

typedef struct (int ** taniche, int valoreDiOttimo)soluzione;

4) un vettore di soluzioni per A e uno per B

soluzione ** A,
B;

---------------------------------------------

dichiaro la base di dati

contenitore ** tanica = ottieniAbbastanzaMemoria(numeroTaniche);

soluzione ** A,
** B;

LIQUIDO A = quantitàDiA,
B = quantitàDiB;

Per la soluzione del problema ci servono una funzione ricorsiva ed una per valutare gli abbinamenti di tutte le soluzioni per A con tutte quelle per B di cui parleremo poi, piano piano.

L'algoritmo per trovare l'ottimo, a livello terra-terra è

1) trovo tutte le combinazioni di taniche che esauriscono completamente A (senza avanzi o disavanzi) e le salvo in un vettore
2) trovo tutte le combinazioni di taniche che esauriscono B A (senza avanzi o disavanzi) e le salvo in un vettore
3) paragono ogni soluzione di A con ogni soluzione di B e valuto

a) se sono compatibili: cioè se non ci sono dei contenitori usati da entrambe le soluzioni, oppure se violano delle altre clausole del problema

b) quanto vale la differenza tra il numero di taniche riepite usando A ed il numero di taniche riempite usando B.

4) confronto la coppia di soluzioni con la coppia che temporaneamente detiene il primato e, nel caso il nuovo valore di ottimo sia migliore, sovrascrivo la precedente.

Se esiste un ottimo, alla fine del procedimento sar trovato.

[Dusy]

ibykos caro...le soluzioni più efficienti sono sempre le più semplici... socialux: ti ho risposto su mrwebmaster...

[ibykos]

Vero, ma non è detto che diano l'ottimo
In ogni caso sono interessato alle altre soluzioni del problema, potreste scriverle qui?

[tia86]

(semi OT)

Ciao, stavo provando anchio a creare il programma ma mi è venuto un dubbio.
In pratica con i contenitori bisogna cercare tutte le possibili combinazioni, ed è qui che ho il dubbio.
Tutte le soluzioni che ho provato o scartano qualche possibilità o sono troppo lente.
Per es. mettiamo che io debba trovare tutte le combinazioni possibili di contenitori, escluse le combinazioni ridondanti e quelle in cui compare piu di una volta il contenitore. In questo modo ho qualcosa come 2 ^ 99 (con 99 contenitori) possibili combinazioni, che sono un pò tantine

Come fare?

[Dusy]

socialux dice:

facciamo che A valga 10 litri e il mio B valga 12 litri,
i contenitori facciamo siano 7 con un array contenente le rispettive capacità...
[5,3,2,6,3,3,6]...ke ne dici?

Dusy dice:

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 e così avanti...


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...

[ibykos]

La soluzione che proponi è "greedy", ovvero non garantisce l'ottimo globale.

[Dusy]

certo che garantisce l'ottimo...
e ti spiego pure perchè...

se sostanza A deve essere distribuita nel MAGGIOR numero possibile di contenitori mentre la B nel MINOR numero di contenitori,
vuol dire che:

- I contenitori utilizzati da A dovranno essere sempre maggiori dei contenitori usati da B, ovvero B potrà utilizzare al massimo la metà dei contenitori altrimenti l'enunciato non sarà più valido...

- Per distribuire più velocemente A e meno B, saranno assegnati ad
A i contenitori più grandi e a B quelli più piccoli.

- La soluzione Ottimale richiede inoltre il minor residuo di A+B

Una volta verificatasi una delle seguenti condizioni:
- Assegnazione ad B della metà dei contenitori...
- Impossibilità di versare B perchè il contenitore è troppo piccolo...
- Esaurimento di B.

si assegneranno i contenitori restanti ad A...

Cosa c'è di sbagliato in tutto questo???

In alternatica fai una matrice N*N elementi, ti trovi tutte le Disposizioni dei bicchieri...e tenti tutte le disposizioni possibili...sinceramente comunque una soluzione del genere è semplicemente illogica e brutale...