posizionare le locandine di un cinema

[alspam]

...non cerco qualcuno che lo risolva ma qualcuno che mi indichi la strada da percorrere...

E' complicato ma immaginate di avere a che fare con le locandine di
un cinema. Ci sono locandine grandi e piccole.
C'e' una struttura che puo' contenere 4 locandine grandi e al massimo
8 locandine piccole.


Ho una tabella di questo tipo:

ID titolo vincolataalbox tipobox tipo colore
1 MARIO 11 2 mostra #CCCCCC
2 LUCA 22 1 mostra #99FF99
3 PAOLO 32 mostra #FF0000
4 ENZO evento #CC66FF
5 GIANNI evento #C2622F


Ho una pagina che dovete immaginare divisa in 4 contenitori.
Ogni contenitore contiene uno o due layer.
Il numero massimo di layer e' 8.
Questi 8 layer si chiamano:
11
12
21
22
31
32
41
42

Ogni riga della tabella e' un layer.
L'altezza di un layer e' definita dal campo tipobox.
Se tipobox=1 allora altezza=105px
Se tipobox=2 allora altezza=210px
La posizione di un layer puo' essere vincolata ad un contenitore,
specificando l'attributo vincolataalbox.

Posso lasciare liberi i campi
vincolataalbox e tipobox
ovviamente il programma deve riempire in maniera "intelligente" lo spazio libero.




Problema.
che logica devo usare per posizionare le locandine ?

Ho pensato questo:
1)uso un vettore di 8 elementi per tenere traccia degli spazi occupati
2)colloco prima i layer vincolati.
3)ogni volta che posiziono un layer vincolato se ne conosco il tipo (grande o piccolo)
"brucio" le posizioni occupate da quel layer sul vettore.

...e qui mi sono fermato perche' non so andare avanti...
l'ID=3 lo potrei posizionare su tipobox grande o piccolo
grande nel caso della tabella che abbiamo ma se ho altre righe potrei valutare
di metterlo piccolo

...mi aiutate nel risolvere questo problema...?

grazie a tutti

[alspam]

mi accorgo che la tabella non e' leggibile allego un'immagine

[alspam]

non vi e' venuto in mente niente in questo we ?

[alspam]

mi hanno detto di usare le tecniche di
BACKTRACKING e CSP

ne avete sentito parlare ?
ma in ASP posso costruire algoritmi di quel tipo ?

[alspam]

per ora siamo arrivati qui, qualcuno ci puo' aiutare ?
vediamo se ho capito...
facciamo una matrice di caratteri, ogni carattere corrisponde ad un box.

il programma inizia mettendo tutte le locandine vincolate nella posizione
corrispondente.

esempio matrici e corrispondenze:
11 21 [ 0 , 0,
12 22 0 , 0 ]

31 41 [ 0 , 0
32 42 0 , 0 ]

dopo la sistemazione delle locandine vincolate avrai:

11 21 [ M , 0,
12 22 M , L ]

31 41 [ 0 , 0
32 42 P , 0 ]

poi il programma lancia la funzione di backtracking che farà tutti i
tentativi possibili
per riempire le rimanenti caselle vuote.
parametri d'ingresso dai le matrici riempite:

***** E' in pseudocodice!

funzioneBackTracking( matrice Box , vettore locandineRimasteDaInserire)
{
if(LocandineRimastedaInserire=vuoto) return 0; //Il programma termina ha
trovato la sozluzione

for(int j =1; j< jnumeroBox ; j++){
for(int i =1; i< inumeroBox ; i++){
if( Box[i,j]= vuota) {

for(int
loc=0;loc<locandinerimastedainserire;loc++){
//toglie la prima locandina da
inserire e prepara
//una matrice temporanea ed un vettore
temporaneo
//inserendo la locandina nel box se
possibile!!!
//ed eliminando la locandina dal
vettore locandineancora da niserire
.......
BoxTemp=Box;
BoxTemp[i,j]=Locandinadainserire[loc]
funzioneBackTracking( BoxTemp,
locandineRimasteDaInserireTemp)

//Questi passi vengono fatti
per ogni locandina
}
}

}


}


Si genera un albero in cui ogni ramo è nua locandina immessa nella
soluzione.

In soldoni

Primo Passo il programma tenta di mettere in11 un'altra locandina
ma è già pieno il box, quindi va in 21 e prova amettere le n locandine
rimaste si
creano così n istanze della funzione backtracking ed in ognuno di questi n
casi
la posizione 21 c'è una locandina diversa.

11 21 [ M , 0,
12 22 M , L ]

31 41 [ 0 , 0
32 42 P , 0 ]


..... boh, non so se si riesce a capire il procedimento....

se non hai mai visto il backtracking devi assolutamente leggertelo un po'.

[alspam]

parto sempre dalla tabellina della fotografia.

lo stato iniziale e'
0 0
0 0
0 0
0 0

posiziono le tre vincolate e la configurazione diventa

M 0
M L
0 0
P 0

(attenzione perche' quando posiziono PAOLO il tuo algoritmo considera
che sia di tipo piccolo)

Ora devo posizionare ENZO e GIANNI.
Supponendo che siano entrambi piccoli, semplicemente potrei scandire
la matrice, trovo un posto vuoto e lo occupo, idem per GIANNI.

Non capisco come prosegue il tuo algoritmo.