Car4m (Normal User)
Newbie
Messaggi: 7
Iscritto: 19/06/2015
|
Buongiorno a tutti!
Spero di risolvere un problema che credo si risolva similmente alla ricerca LIS. VEDASI IL TESTO ALLEGATO
Ma non son sicuro sicuro
Codice sorgente - presumibilmente C++ |
#include <string.h> #include <fstream> #include <iostream> #include <climits> using namespace std; typedef struct{ int x,y,z; }box; ifstream in ("in.txt"); ofstream out ("out.txt"); int max_box(box *a, int dim); int ricbin(box *a, int T[], int l, int r, box elemento); int main(void) { int dim; in >> dim; box a[dim]; for(int j=0; j<dim; j++) in >> a[j].x >> a[j].y >> a[j].z; out<< "TOTALE: " << max_box(a, dim)<<endl; return 0; } int ricbin(box *a, int T[], int l, int r, box elemento) { int m; while( r - l > 1 ) { m = l + (r - l)/2; if( a[T[m]].x >= elemento.x && a[T[m]].y >= elemento.y && a[T[m]].z >= elemento.z ) r = m; else l = m; } return r; } int max_box(box *a, int dim) { int *indicicoda = new int[dim]; int *indicipreced = new int[dim]; int lung; memset(indicicoda, 0, sizeof(indicicoda[0])*dim); memset(indicipreced, 0xFF , sizeof(indicipreced[0])*dim); indicicoda[0] = 0; indicipreced[0] = -1; /* punta sempre alla posizione vuota */ lung = 1; for( int i = 1; i < dim; i++ ) { if( a[i].x < a[indicicoda[0]].x && a[i].y < a[indicicoda[0]].y && a[i].z < a[indicicoda[0]].z ) { /* se abbiamo un nuovo valore più piccolo */ indicicoda[0] = i; } else if ( a[i].x > a[indicicoda[lung-1]].x && a[i].y > a[indicicoda[lung-1]].y && a[i].z > a[indicicoda[lung-1]].z ) { // a[i] vuole trovare la più grande sottosequenza crescente indicipreced[i] = indicicoda[lung-1]; indicicoda[lung++] = i; } else { // a[i] potrebbe essere nella sottosequenza finale e quindi potrebbe rimanere in indicicoda int pos = ricbin(a, indicicoda, -1, lung-1, a[i]); indicipreced[i] = indicicoda[pos-1]; indicicoda[pos] = i; } } /* stampa la sequenza finale risultante, dal più grande intero al più piccolo intero */ for( int i = indicicoda[lung-1]; i >= 0; i = indicipreced[i] ) out << a[i].x <<"x"<<a[i].y<<"x"<< a[i].z<<endl; //out << endl; delete[] indicicoda; delete[] indicipreced; return lung; }
|
Se in input diamo 3 box:
Codice sorgente - presumibilmente Plain Text |
Allora non ci sono problemi.
Ma se abbiamo input disordinati...
Codice sorgente - presumibilmente Plain Text |
Non va... Dovrebbe restituire lo stesso output di prima perché si inseriscono una dentro l'altra (come nel caso precedente).
Ed il problema è proprio il LIS che non "guarda indietro".
Che modifiche dovrei fare?
SPERO TANTO IN UN VOSTRO AIUTO
PS: Non si può ordinare in alcun modo... Se no problema risolto
In allegato leggere punto 1 e poi il 3 per la stampa finale Ultima modifica effettuata da Car4m il 24/06/2015 alle 9:46 |
|
pierotofy (Admin)
Guru^2
Messaggi: 6230
Iscritto: 04/12/2003
|
|
|
Car4m (Normal User)
Newbie
Messaggi: 7
Iscritto: 19/06/2015
|
Ciao Piero!
Non si può ordinirare, la "pre-elaborazione" non è consentita.
Avevo pensato anch'io ad ordinarli per volumi ma non si può rileggendo il testo allegato
Effitivamente, il testo, è un pochetto ambiguo; diciamo che ci "forza" a vederle/rivederle tutte, così come vengono date, con la PD.
Ultima modifica effettuata da Car4m il 22/06/2015 alle 16:54 |
|
pierotofy (Admin)
Guru^2
Messaggi: 6230
Iscritto: 04/12/2003
|
Non si può ordinirare, la "pre-elaborazione" non è consentita.
|
Perchè no? Il testo che hai allegato non lo proibisce. O forse ho interpretato male.
edit: ah, usando un algoritmo DP. Quindi si, non si deve ordinare.
Una scatola Si può essere inserita in una scatola Sj solo se Si sottoinsieme di Sj e i < j
|
Per:
3
3 3 3
2 2 2
1 1 1
Nel caso in cui:
Si = 2 2 2 (i = 1)
Sj = 3 3 3 (j = 0)
i < j è falso. Quindi il tuo input non è valido (o il risultato è 0).
Ultima modifica effettuata da pierotofy il 22/06/2015 alle 19:09
|
|
Car4m (Normal User)
Newbie
Messaggi: 7
Iscritto: 19/06/2015
|
Esatto!
Tu cosa consigli di fare?
2 cicli uno dentro l'altro quindi
Codice sorgente - presumibilmente Plain Text |
In questo caso, parlando in C++ , come si potrebbe fare in modo efficente?
---------
con input:
3
3 3 3
2 2 2
1 1 1
Dovrebbe riuscire a stampare:
3 3 3
2 2 2
1 1 1
TOTALE 3
---------
Poiché 1 1 1 può stare dentro 2 2 2, così 2 2 2 può essere contenuta in 3 3 3.
Ultima modifica effettuata da Car4m il 22/06/2015 alle 22:22 |
|
pierotofy (Admin)
Guru^2
Messaggi: 6230
Iscritto: 04/12/2003
|
No, leggi la mia risposta.
|
|
Car4m (Normal User)
Newbie
Messaggi: 7
Iscritto: 19/06/2015
|
Letta e riletta certo, forse allora non ho afferrato.
Devo cambiare proprio "strategia" o, almeno, sono sulla retta via?
|
|
pierotofy (Admin)
Guru^2
Messaggi: 6230
Iscritto: 04/12/2003
|
Questo input:
3 3 3
2 2 2
1 1 1
Deve stampare:
TOTALE 0
Una scatola Si può essere inserita in una scatola Sj solo se Si sottoinsieme di Sj e i < j
|
La clausola "e i < j" praticamente dice che l'ordine conta!
i e j sono indici. 3 3 3 ha indice 0, 2 2 2 ha indice 1 e 1 1 1 ha indice 2.
Ad esempio non puoi confrontare 2 2 2 (i) e 3 3 3 (j), perchè anche se 2 2 2 < 3 3 3, i = 1 e j = 0, quindi i < j é falso e quindi, 2 2 2 non può essere inserita in 3 3 3.
|
|
Car4m (Normal User)
Newbie
Messaggi: 7
Iscritto: 19/06/2015
|
Cavoli non l'avevo notato!
(Forse una sola la può restituire però)
Devo chiedere all'autore dell'esercizio cosa intendesse.
Piero Grazie!
Quindi la soluzione è banalmente fatta col metodo LIS (di cui sopra) ?
Ma se volessimo interpretare il testo, così come "intendevo io" , serve almeno un while interno al for?
Ho provato ma c'é sempre qualcosa che non va
Ultima modifica effettuata da Car4m il 23/06/2015 alle 10:32 |
|