Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Problema  (Citit de 1117 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
sken3r
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« : 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
Memorat
dushmi
Nu mai tace
*****

Karma: 130
Deconectat Deconectat

Mesaje: 472



Vezi Profilul
« Răspunde #1 : 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)
  for (int j = S; j >= 0; -- j)
    if (s[j] && j + cost[i] <= S) {
      s[j + cost[i]] = 1;
      pred[j + cost[i]][ ++ lung[j + cost[i]]] = j;
    }

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) Smile. Oricum pentru valori mari cred ca exista prea multe drumuri pentru a fi afisate toate.

Oricum enuntul mi se pare destul de "vag" Eh?... Ar putea merge si cu Backtracking Confused

« Ultima modificare: Mai 05, 2011, 21:16:21 de către Dusmanu Mihai-Alexandru » Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines