Titlul: Problema Scris de: Igor Mu din Mai 05, 2011, 19:53:34 Un grup isi propune un traseu prin niste cabane, costrile cazarii pentru o noapte la fiecare cabana se citesc de la tastatura pentru fiecare din cele N cabane. Grupul dispune de S lei. Sa se afiseze toate traseele prin cabane(nu neaparat toate) ce nu depaseste suma S, stiind ca la o cabana nu se sta decit exact o zi si ca nu se revine la o cabana vizitata exemplu: 1-2-1, 3-5-3
ceva sugestii propuneri parere?? Mersi anticipat Titlul: Răspuns: Problema Scris de: Mihai-Alexandru Dusmanu din Mai 05, 2011, 21:09:49 Daca am inteles bine problema, atunci ar merge sa faci un fel de rucsac si pentru fiecare suma sa retii intr-un vector predecesorii.
ceva de genu Cod: for (int i = 1; i <= nrc; ++ i) si dupa setezi cate o suma <= S si iei toti predecesorii la rand. Solutia asta nu merge decat in cazul in care numarul de cabane si S-ul sunt acceptabile ( ca valori) :). Oricum pentru valori mari cred ca exista prea multe drumuri pentru a fi afisate toate. Oricum enuntul mi se pare destul de "vag" :-s... Ar putea merge si cu Backtracking :-? |