Acum este Joi Aug 21, 2014 4:22 am
Text

Programare / Web Design

problema programare dinamica

Despre PHP, MySQL, HTML, C++, VB, JAVA etc.

problema programare dinamica

Mesajde raptor » Joi Apr 27, 2006 6:24 pm

Mai fac din cand in cand probleme in C++ de pe ace.delos.com\usacogate (trebuie cont pentru a putea vedea problemele ) si m-am cam blocat la o problema aparent simpla. Suna cam asa
: avand un sistem monetar cu V monede v1..vn si un nr n trebuie sa gasim nr de posibilitati de a forma suma n cu monedele v1..vn.
EX: 3 monede 1 2 5
n=10 vom avea 10 posibilitati: 5+5, 5+2+2+1 etc
Acum ideea e ca programul trebuie sa fie si eficient(mie imi iese din timp la al 3-lea test).Am inteles ca ar trebui rezolvat cu programare dinamica dar nu prea vad cum as putea face asta. Poate aveti voi vreo idee.Eu am incercat cam cu brute force dar ia cam 12 sec la
v=10 n =100 si 1 2 3 4 5 6 7 8 9 10.
For a list of all the ways technology has failed to improve the quality of life, please press three.
Avatar utilizator
raptor
 
Mesaje: 546
Membru din: Joi Iul 03, 2003 9:25 pm
Localitate: Sinaia/Bucuresti

Mesajde mirku » Joi Apr 27, 2006 6:29 pm

pai io cred k chestia asta o poti face numai cu backtraking (nush daca asa se scrie). faci toate posibilitatile si apoi le afisezi sau ceva!

dacă ai nevoie de mai multe detalii, shout here!
m!rKu :: :) :: Be FREE to LIVE!
click aici!
Avatar utilizator
mirku
 
Mesaje: 38
Membru din: Mar Iul 19, 2005 10:12 pm
Localitate: NU AICI

Mesajde The Beast » Joi Apr 27, 2006 7:13 pm

yeap. se face cu backtracking, desi e posibil si cu ceva dinamic.
O sa caut prin cpp-urile de anul trecut si daca o gasesc, ca stiu ca am facut-o revin si dau un edit .
Avatar utilizator
The Beast
 
Mesaje: 2487
Membru din: Mie Iun 04, 2003 10:45 am

Mesajde raptor » Joi Apr 27, 2006 7:33 pm

backtracking ma descurc dar iese cu mult din timp, stiu ca mai era prin liceu o kestie cu partitiile unui nr si poate s-ar putea adapta ala, dar nu mai stiu exact cum e.
For a list of all the ways technology has failed to improve the quality of life, please press three.
Avatar utilizator
raptor
 
Mesaje: 546
Membru din: Joi Iul 03, 2003 9:25 pm
Localitate: Sinaia/Bucuresti

Mesajde mirku » Vin Apr 28, 2006 6:23 pm

pai nu prea vad cum s-ar mai putea face pentru ca nu stii ce monede ti se dau! deci trebuie sa le iei dintr-un sir si sa le folosesti! nu cred k poti face cu partitii si alte metode (din cate stiu eu)
m!rKu :: :) :: Be FREE to LIVE!
click aici!
Avatar utilizator
mirku
 
Mesaje: 38
Membru din: Mar Iul 19, 2005 10:12 pm
Localitate: NU AICI

Mesajde raptor » Sâm Apr 29, 2006 10:56 am

poate m-am exprimat prost, monedele se dau ,le-am notat eu cu v1,...,vn, dar in exemplu am zis sunt 3 monede , 1,2 si 3 si suma la care trebuie ajuns este 10. se considera ca ai numar nelimitat de monede din fiecare fel.Astfel vor fi 10 combinatii:
1+1+1+1+1+1+1+1+1+1
1+1+1+1+1+1+1+1+2
1+1+1+1+1+1+2+2
1+1+1+1+2+2+2
1+1+2+2+2+2
2+2+2+2+2
1+1+1+1+1+5
5+5
1+2+2+5
1+1+1+1+1+5
Oricum am nevoie doar de nr lor, nu trebuie sa le si afisez.
For a list of all the ways technology has failed to improve the quality of life, please press three.
Avatar utilizator
raptor
 
Mesaje: 546
Membru din: Joi Iul 03, 2003 9:25 pm
Localitate: Sinaia/Bucuresti

Mesajde mirku » Sâm Apr 29, 2006 2:17 pm

pai stai putin.... monedele se dau de la tastatura sau sunt 1,2,3,.....
daca se dau de la tastatura atunci nu le stii si trebuie backtrcking! daca nu, cred ca se poate si altfel da eu nu stiu.
m!rKu :: :) :: Be FREE to LIVE!
click aici!
Avatar utilizator
mirku
 
Mesaje: 38
Membru din: Mar Iul 19, 2005 10:12 pm
Localitate: NU AICI

Mesajde iLogiK » Sâm Apr 29, 2006 3:07 pm

mirku, daca citesti primul post vezi raspunsul la intrebarea ta.
raptor, posteaza pls functia ta de backtracking
Avatar utilizator
iLogiK
 
Mesaje: 3189
Membru din: Mar Aug 12, 2003 10:37 pm
Localitate: Oradea / Timisoara

Mesajde 2good4you » Dum Apr 30, 2006 6:02 pm

pey mere cu programare dinamica
deci se face aşa:
se ia una bucata vector,fiekre indice semnifica o moneda..
de fiecare când aduni u pui in v[i]suma la care ai ajuns pana acuma..park ceva de genu era
ma mai uit ji-ti zic exakt
Intel inside idiots outside
Avatar utilizator
2good4you
 
Mesaje: 181
Membru din: Joi Mar 03, 2005 1:49 pm

Mesajde raptor » Lun Mai 01, 2006 4:41 pm

asta e una din variante, nu singura :)

Cod: Selectaţi tot
int num(int n,int k)
{
if(n==0) return 1;
if(k<0) return 0;
if(n<0) return 0;
return num(n,k-1)+num(n-m[k],k);

}

For a list of all the ways technology has failed to improve the quality of life, please press three.
Avatar utilizator
raptor
 
Mesaje: 546
Membru din: Joi Iul 03, 2003 9:25 pm
Localitate: Sinaia/Bucuresti

Mesajde iLogiK » Mar Mai 02, 2006 6:39 pm

okay, nu prea recunosc metoda ta de backtracking dar mi se pare foarte ineficienta (se apeleaza de 2 ori functia la fiecare aplare)

citeste mai jos varianta mea.
n-am incercat codul pentru ca nu am c-ul aici (l-am scris din cap)....in varianta finala (adica dupa ce rezolvi unele chestii care mai mult ca sigur mi-au scapat pentru ca nu am putut sa il testez) ar trebui sa mearga mai repede decat ce ai postat tu acolo, desi nu stiu cum se va comporta in exemplul tau cu n=100....
Cod: Selectaţi tot
int s[100]; //stiva cu solutii
int st; //suma obtinuta prin adunarea solutiilor din stiva la un anumit moment
int n; //valoarea care trebuie obtinuta
int nm; //numarul de tipuri de monede
int m[100]; //monedele

void back(int k)
{
  if (st>=n)
  {
    if (st==n) afisare_solutii(k); //un for de la i la k-1 cu cout<<m[s[i]]<<" ";
  } else
  {
   for (i=0;i<nm;i++)
  {
     /*o mica optimizare...ca sa nu se reia solutii identice dar in alta ordine
     (si sa se execute mai repede programul):
     daca nu e la prima moneda, se incepe automat de la valoare monedei precedente (proctic se iau monedele in ordine crescatoare)*/
     if (k!=0 && i<s[k-1]) i=s[k-1];

     s[k]=i;
     st+=m[i];
     back(k+1);
     s-=m[i];
  }
  }
}
Avatar utilizator
iLogiK
 
Mesaje: 3189
Membru din: Mar Aug 12, 2003 10:37 pm
Localitate: Oradea / Timisoara

Mesajde raptor » Mar Mai 02, 2006 9:18 pm

am incercat si ceva asemanator cu ce ai scris tu acolo, dar tot iese din timp, sunt 90% sigur ca nu merge cu backtracking, ce am scris mai sus e dupa o idee de pe alt forum unde cineva zicea ca asa ar intra in timp, desi nu vad cum, am zis ca e una din variante. In plus nu testul cu 100 e cel mai mare ci unul cu 100.000
For a list of all the ways technology has failed to improve the quality of life, please press three.
Avatar utilizator
raptor
 
Mesaje: 546
Membru din: Joi Iul 03, 2003 9:25 pm
Localitate: Sinaia/Bucuresti

Mesajde badicuady » Joi Mai 04, 2006 11:47 am

Poate te ajuta asta!
Problema rucsacului pentru intregi

Se dau N (tipuri de) obiecte cu dimensiuni si si valori vi intregi. Care e valoarea maxima a unor obiecte de dimensiune totala data D?

Problema rucsacului are multe variante !
Daca se permit fragmente de obiecte, problema are solutie greedy. Daca dimensiunile sunt reale, problema e NP-completa (exponentiala).

Varianta 1: numar nelimitat de obiecte de fiecare tip:
for (d = 1; d <= D; ++d) /* succesiv pt. dimensiuni crescatoare */
for (c[d] = i = 0; i < n; ++i) /* incearca fiecare obiect i */
if (s[i] < d && (m = c[d-s[i]] + v[i]) > c[i]) c[i] = m;

Varianta 2: obiecte unice; c[d][i]: cost max. pt. dim. d, obiecte 0..i
for (d = 1; d <= D; ++d) /* succesiv pt. dimensiuni crescatoare */
for (i = 0; i < n; ++i) /* incearca includerea obiectului i */
if (s[i] < d) c[d][i] = max(c[d][i-1], c[d-s[i]]+v[i])


Ma straduiesc sa adaptez pentru problema asta! Revin ASAP! [smilie=Respect.gif]
Sam I am! :D
Imagine
Avatar utilizator
badicuady
 
Mesaje: 412
Membru din: Lun Dec 05, 2005 11:14 pm
Localitate: Brasov

Mesajde raptor » Vin Mai 05, 2006 2:00 pm

am gasit cum se facea, destul de simplu ,dar de ,nu m-am prins singur, multumesc tuturor pentru sugestii
Trebuia sa avem un vector de la 0 pana la n-nr-ul cautat si apoi:
Cod: Selectaţi tot

 
  nway[0] = 1;
  for (i=0; i<v; i++) {
    c = coin[i];
    for (j=c; j<=n; j++)
      nway[j] += nway[j-c];
  }




mai multe aici:
http://www.comp.nus.edu.sg/~stevenha/pr ... ing_Change
For a list of all the ways technology has failed to improve the quality of life, please press three.
Avatar utilizator
raptor
 
Mesaje: 546
Membru din: Joi Iul 03, 2003 9:25 pm
Localitate: Sinaia/Bucuresti

Mesajde charon » Vin Mai 12, 2006 11:01 am

daca vrei sa faci ceva cat mai general incearca sa folosesti STL (sa nu fi ingradit de dimesiuni fixe pt vectori sau alocare de memorie ineficienta sau care nu e necesara) - vezi http://www.cppreference.com
Vampires vs Werewolves. Join the fight !
http://s3.bitefight.org/c.php?uid=45553
Avatar utilizator
charon
 
Mesaje: 120
Membru din: Lun Apr 03, 2006 3:54 pm
Localitate: atarnat de un soarec


Înapoi la Programare / Web Design

Autentificare

Autentifică-mă automat la fiecare vizită