Però ho fatto una bella confusione, ho preso alcuni pezzi da quella dove considero X fra quelli meno lunghi e quella dove non lo considero. Ci sono alcuni casi dove pure se X è quello più alto non conviene escluderlo. Per esempio con 3 galli (H,L) così: (1,1), (3,4), (7,8) e pozzo profondo 16, l’ultimo è l’unico che può uscire. Secondo me va sfruttato meglio il fatto di aver ordinato l’array, perchè così non è mai stato usato il fatto di averlo ordinato.
Per esempio con 3 galli (H,L) così: (1,1), (3,4), (7,8) e pozzo profondo 16, l'ultimo è l'unico che può uscire.Sì, e infatti questa è la soluzione che viene trovata da quell'algoritmo...Luke
Insomma, quello con lunghezza totale maggiore è il terzo. Ma così com'è non riesce a uscire, dunque scarto, tra gli altri due, il secondo (quello di altezza massima) e decremento la profondità di 3. Ora può uscire, quindi passo al successivo (il primo, visto che il secondo è stato scartato). Anche salendo sopra il terzo, non riesce a uscire: ancora una volta, devo scartarne uno, ma l'unico rimasto è lui stesso, ergo ho concluso.
ma c’erano altri casi in cui conveniva togliere X quando è il più alto. Ad esempio con un pozzo di profondità 10 e galli del tipo (0,7) (0,7) (0,7), (3,6)
ma c'erano altri casi in cui conveniva togliere X quando è il più alto. Ad esempio con un pozzo di profondità 10 e galli del tipo (0,7) (0,7) (0,7), (3,6)Anche per questo funziona: parto dal quarto gallo, che ha lunghezza 9. Siccome non riesce a uscire, devo scartare il più alto tra quelli con lunghezza minore o uguale di 9 (quindi compreso egli stesso). Ma in questo caso il più alto è proprio lui, quindi lo scarto e poi vedo che gli altri tre possono essere presi tutti.Luke
Gli unici casi particolari da trattare, a questo punto, credo siano quelli in cui dobbiamo effettuare una scelta tra due galli con la stessa altezza/lunghezza. Ad esempio, a parità di altezza conviene scartare il gallo che ha le braccia più corte.
non sto capendo, non hai operato diversamente in quei 2 casi? In uno hai considerato X, nell’altro solo i rimanenti.
Ok, è vero, hai ragione… :S
Non saprei, ora non ho molto tempo, ma forse va scartato quello con lunghezza delle braccia minima tra quelli che hanno altezza sufficiente a far uscire l’altro. O forse è proprio l’approccio greedy che è sbagliato…
Boh i problemi di scelta e di costo minimo di solito sono o di DP o Greedy e dai limiti del problema direi che una DP è improbabile (mi fa storcere il naso pure il fatto che i galli “nella pratica” puoi riorganizzarli ogni volta, non è tipo Poldo/Torri)
Mi rassegno, è meglio se penso a quelli più semplici, non a quelli che risolvono solo in 3 dove servono magie
secondo me l’idea non è malvagia…
E poi vi siete fissati a trovare un senso a quell’esempio quando tra le assunzioni le H sono tutte > 0
Non va bene comunque, ho trovato vari controesempi con le H e le L tutte > 0 che non si risolvono con la strategia greedy (almeno non con quella che abbiamo utilizzato sin ora).E poi vi siete fissati a trovare un senso a quell'esempio quando tra le assunzioni le H sono tutte > 0VashTheStampede
Per esempio, prendi un pozzo profondo 6 e 3 galli (1, 4), (2, 2), (1, 1): visto che il primo non riesce a uscire dovremmo scartare il secondo (quello più alto), ma in questo modo otteniamo una soluzione che non è ottima (riesce a uscire solo il primo); invece, sacrificando il terzo riuscirebbero a salvarsi i primi due (prima esce il secondo e poi il primo)...
Forse l’algoritmo è di tutt’altro tipo. Quel suggerimento non l’abbiamo mai usato veramente.
Oggi a scuola ne ho pensata un’altra simile. Qualcuno riesce a smontarmela?
Ordiniamo stavolta solo in base alla lunghezza delle braccia, partendo da quello con le braccia più corte e terminando con quello dalle braccia più lunghe.
Un gallo è in grado di uscire dal pozzo solo se la lunghezza delle sue braccia sommata all’altezza di tutti i galli tra cui sè stesso è maggiore della profondità del pozzo.
Avendo ordinato in base alla lunghezza delle braccia, siamo subito in grado di capire da che punto in poi i galli hanno speranze di uscire. Basta controllare da che punto in poi la lunghezza delle braccia è maggiore della profondità del pozzo meno l’altezza complessiva dei galli.
Quindi percorrendo l’array delle lunghezze dall’inizio, scartiamo tutti i galli che non raggiungono la lunghezza necessaria. Appena arriviamo ad un gallo che potenzialmente può uscire, vuol dire che tutti i galli da lui in poi potrebbero uscire. Facciamo quindi uscire quello più basso che è quello che pesa di meno sui rimanenti. Sommiamo la sua altezza alla profondità del pozzo e continuiamo ad iterare l’array delle lunghezze nel punto in cui eravamo rimasti. Quindi togliamo di nuovo i galli che non possono uscire e appena troviamo un gallo che può uscire, possono uscire pure tutti quelli davanti a lui, e faccio uscire quello più basso.
Stavolta funziona?
Stavolta funziona?
Notare che stavolta i galli che escono, salgono sopra tutti gli altri, non solo su quelli più lunghi.
Questa funziona su tutti gli esempi fatti fino ad ora e anche sull’esempio del testo. Ho buone speranze!
Nella pratica ordini i galli per l’altezza e dal più basso al più alto valuti se può uscire o meno. :<div>E in ogni caso non è detto che se uno con le braccia lunghe L riesce ad uscire allora tutti quelli che hanno le braccia più lunghe delle sue potranno uscire! 
principalmente li ordino per lunghezza delle braccia, altrimenti non posso fare quella cosa. Poi se prendere il più basso tra quelli che hanno lunghezza braccia maggiore di X era nlogn prima non vedo perchè non lo sia adesso no?
[Modifico] Ho letto ora la tua modifica. Non ho detto che possono uscire TUTTI, ma ho detto che potenzialmente possono uscire. E questo è sicuro. Quindi faccio uscire SOLO il più basso tra quelli che hanno braccia più lunghe e continuo come prima.
No scusami sono io un idiota non ho considerato il fatto che tutti beneficiano dell’altezza di tutti quando sono in cima! Ultimamente mi perdo in banalità x__x
Pure io mi perdo in banalità x_x Quindi ora ti convince? Sono sicuro che funziona sugli esempi visti fin’ora. Se sapessi farlo la implementerei. Forse provo col counting sort, l’unico che so implementare
Usa la funzione sort() della libreria <algorithm> (nel namespace std).
sort implementa (mi sembra) l’IntroSort, una versione ottimizzata del QuickSort.
http://www.cplusplus.com/reference/algorithm/sort/
La mia difficoltà è che io non vorrei che l’array ordinato contenesse i valori delle lunghezze o delle altezze, ma vorrei che contenesse gli indici dei galli. Come posso fare a tal scopo?
Anzi credo di aver capito! Molte grazie, non avevo letto bene
Comunque non vorrei dire stupidaggini: il tuo algoritmo fa la stessa cosa di un banale ordinamento secondo H (crescente) e far uscire ogni volta il primo che ce la fa!
Solo che tu lo fai al contrario, cioè tra tutti quelli che riescono ad uscire prendi il più basso! :v