.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Progetto] Samegame3 (http://www.dsy.it/forum/showthread.php?threadid=33907)

se in intendi come trovare il massimo punteggio realizzabile, basta ordinare i totali, esempio:

colonne -1(totale=8) 0(totale=7) 1(totale=6) 2(totale=8)

ordinando i totali ottengo: 6 7 8 8

scorro la lista in questo modo 8->8->7->6 controllando ad ogni passo se ci sono colonne vicine gia cancellate...

alla fine ottengo 16 (cancello colonne -1 e 2)

ah!!! bastava usare il semplice trucco di ordinare le colonne... e io che m stavo tirando scemo cercando calcolare tutte le combinazioni.... vabbè meglio così...
grazie dell'aiuto

scusa larios ma sono un po' dubbioso sulla tua tecnica...
ad esempio se la combinazione di colonne che ha il totale + alto nn comprende la colonna con il valore + alto in assoluto sono fregato...ad esempio:

col1 tot = 5;
col2 tot = 10;
col3 tot = 6;
con la tua tecnica cancellerei solo la col2 che ha totale 10;
mentre invece devo cancellare la col1 e col3 con il totale di 11...

quindi forse l'unica soluzione è calcolare il tot della combinazione che fa il maggior punteggio usando la porgrammazione dinamica, che mi consente di riciclare i risultati di sottoproblemi memorizzandoli da qualche parte senza star a dover ricalcolarli qualora gli stessi sotto-problemi si ripresentassero...

qualcuno può dare qualche informazione su come ha implementato la funzione "minore"??????

Originally posted by imperator
scusa larios ma sono un po' dubbioso sulla tua tecnica...
ad esempio se la combinazione di colonne che ha il totale + alto nn comprende la colonna con il valore + alto in assoluto sono fregato...ad esempio:

col1 tot = 5;
col2 tot = 10;
col3 tot = 6;
con la tua tecnica cancellerei solo la col2 che ha totale 10;
mentre invece devo cancellare la col1 e col3 con il totale di 11...

quindi forse l'unica soluzione è calcolare il tot della combinazione che fa il maggior punteggio usando la porgrammazione dinamica, che mi consente di riciclare i risultati di sottoproblemi memorizzandoli da qualche parte senza star a dover ricalcolarli qualora gli stessi sotto-problemi si ripresentassero...

avevo provato un po di soluzioni simili, dividendo in sottoproblemi di ordine 2 tipo
(2,40)(50,20)(1,5)(100)
provando a tenere il maggiore per ogni insieme dopo un confronto sulle adiacenze ... ma non ha funzionato..
sono molto orientato a sviluppare con la programmazione dinamica, salvandomi i risultati volta a volta come diceva imperator

e ma tu ad esempio in una soluzione puoi avere:
(supposto che il blocco abbia 10 colonne, numerate da 1 a 10)
sia la soluzione ottima composta dalle colonne 1, 4, 7,9.
ad esempio qui hai dei salti irregolari...
credo tu stia cercando di trovare la soluzione ottima direttamente, cercando attraverso determinati stratagemmi di scartare determinate colonne a prescindere, cercando così di costruire un'unica soluzione, quella ottima...
però qua devi per forza (credo) calcolarti tutte le possibili combinazioni... non ci sono algoritmi che ti consentono di prendere direttamente le colonne della combinazione migliore, la combinazione con il punteggio + alto...

rimane il calcolo delle conbinazioni .. ma rischiano di diventare veramente reoppe per valori attorno alle 15 colonne
n!/(k!*(n-k)!)

tieni presente che non sono delle vere e proprie combinazioni matematiche... hai la regola che se cancelli la colonna x non puoi cancellare la colonna x-1 e x+1...

Originally posted by gicagi
qualcuno può dare qualche informazione su come ha implementato la funzione "minore"??????

nella struttura dell'albero rb che campi avete inserito? usate solo i puntatori? e dite che bastano solo i puntatori *left, *right e *up o bisogna aggiungerne uno *down?

help!

ma già con i puntatori left e right discendi l'albero...a sx o dx..
io personalmente non ho aggiunto altri puntatori

quindi la struttura di ogni nodo sarebbe una biglia con le coordinate, il valore e il colore?

perchè non mi è chiaro come usare gli alberi per spostarmi all'interno della scacchiera..

esatto le informazioni che ti servono all'interno di ogni biglia sono coordinate, colore, valore

ok, però ad esempio se il nodo A contiene la biglia in posizione (x,y), i suoi figli conterranno le biglie in quale posizione?

non sono molto ferrato con gli alberi!

edit: avevo pensato a fare in modo che i figli a sinistra di un nodo fossero quelli adiacenti per le ascisse, mentre quelli a destra fossero adiacenti per le ordinate, ma mi escono dei doppioni.