Tema Programare Dinamica

Buna!! Incerc si eu sa invat programarea dinamica,dar nu am gasit pe net ceva din care sa pot intelege calumea.M-am uitat peste tutorialul de pe topcoder am inteles cat de cat in afara de partea cu grafuri(care nu le stiu pentru ca  nu cred ca trebuie la olimpiada la a X-a),m-am uitat si peste rezolvarea la problema rucsacului de pe infoarena,dar cand incerc sa fac probleme cu programare dinamica nu am nici o idee.....:|

Ma puteti ajuta sa-mi explicati mai bine programarea dinamica si eventual sa-mi dati ceva probleme(pt. incepatori) sa rezolv ??

Edited by Mitza444, 02 September 2011 - 20:59.

Nu exista un algoritm universal, ci mai degraba un mod de gandire. Ia cartea Emanuelei Cerchez, "Programarea in limbajul C/C++ pentru liceu", Editura Polirom, volumul 2, o buna parte e despre programarea dinamica, poate te ajuta mai mult decat te poate ajute cineva pe forum.

Programarea dinamica  poate fi considerata cea mai grea metoda de programare. Cum am mai zis, ea presupune sa poti sa abstractizezi problema, sa o imparti in subprobleme pe care le rezolvi independent si le combini dupa o formula/o anumita logca pentru a obtine raspunsul. Cum a zis si @edy_3dz nu exista un anumit tipar, trebuie doar multa munca pentru a-ti da seama cum se pune problema. Acea problema a rucsacului se rezolva ca si prima problema prezentata in tutorialul de pe topcoder. Uite niste probleme de dinamica pentru incepator ( logic ca unele problemele se pot rezolva, poate mai simplu, si fara programare dinamica )  :
http://infoarena.ro/problema/scmax
http://community.top...l...ent&pm=1259
http://community.top...l...402&rd=5009
http://infoarena.ro/problema/ssm
http://infoarena.ro/problema/podm
http://community.top...l...918&rd=5006
http://infoarena.ro/problema/stirling
http://campion.edu.r...g...de&id=32752
http://campion.edu.r...g...de&id=27129
http://campion.edu.r...g...view&id=513
http://campion.edu.r...g...view&id=793
http://campion.edu.r...g...view&id=344
http://campion.edu.r...g...view&id=485
http://campion.edu.r...g...view&id=599
http://campion.edu.r...g...iew&id=1240
http://campion.edu.r...g...iew&id=1079
http://fiicompetitio...t_viena_2_3.pdf
http://fiicompetitio..._sablon_2_4.pdf
http://infoarena.ro/problema/cmlsc
http://infoarena.ro/problema/rmq
http://infoarena.ro/problema/lca
http://infoarena.ro/problema/hamilton

Am incercat sa rezolv problema pachete de pe .campion si am gasit o recurenta ,dar nu e chiar buna pt. ca la unele teste cum ar fi exemplul 2 nu merge.......
Va puteti uita un pic peste cod sau sa-mi dati niste indicatii cum sa fac problema:D

#include<cstdio>
using namespace std;
int max(int a, int {
	if(a>b)return a;
return b;
}
int min[100001],d[100001],i[100001];
int main(){
	int n,k;
	FILE * pFile;
	pFile=fopen("pachete.in","r");
	fscanf(pFile,"%d",&n);
	for(k=1;k<=n;k++){
		fscanf(pFile,"%d%d",&i[k],&d[k]);
	}
	for(k=1;k<=n;k++){
		min[k]=d[k]+max(0,min[k-1]-i[k]);
	}
	pFile=fopen("pachete.out","w");
	fprintf(pFile,"%d",min[n]);
	return 0;
}

Secretalex92 mai poti pune o data linku de la primele 2 probleme de pe .campion pt. ca atunci cand dai click pe link imi intra pe campion si imi da "eroare acces interzis"......

Mda am reusit pana la urma sa rezolv problema de 100p dar nu stiu sigur daca am folosit programare dinamica
Va puteti uita peste cod sa-mi ziceti daca e programare dinamica sau nu si daca nu e cum as putea face cu programare dinamica??

#include<cstdio>
using namespace std;
int max(int a, int {
	if(a>b)return a;
return b;
}
int d[100001],i[100001];
int main(){
	int n,k,dif,min;
	FILE * pFile;
	pFile=fopen("pachete.in","r");
	fscanf(pFile,"%d",&n);
	for(k=1;k<=n;k++){
		fscanf(pFile,"%d%d",&i[k],&d[k]);
	}
	min=d[1];
	for(k=2;k<=n;k++){
		dif=d[k]-i[k-1];
		min=min+max(0,dif);
		if(dif<0)i[k]=i[k]-dif;
	}
	pFile=fopen("pachete.out","w");
	fprintf(pFile,"%d",min);
	return 0;
}

Da este dianmica
http://campion.edu.r...g...view&id=261
http://campion.edu.r...g...iew&id=1072

Imi puteti spune de ce imi da ciclu infinit si dupa aceea eroare??problema este lacusta de  pe .campion

#include<cstdio>
using namespace std;
int A[101][101],B[101][101];
int main(){
	int m,n,i,j,x,y,x1,y1,min;
	FILE * pFile;
	pFile=fopen("lacusta.in","r");
	fscanf(pFile,"%d%d",&m,&n);
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
			fscanf(pFile,"%d",A[i][j]);
		}
	}
	B[2][1]=99999;
	min=99999;
	for(i=2;i<=n;i++){
		B[2][i]=A[1][1]+A[1][i]+A[2][i];
		if(B[2][i]<min){x=2;y=i;min=B[2][i];}
	}
	for(i=3;i<=m;i++){
		min=99999;
		for(j=1;j<=n;j++){
			if(y!=j){
			B[i][j]=A[i-1][j]+A[i][j]+B[x][y];
			if(B[i][j]<min){min=B[i][j];x1=i;y1=j;}
			}
		}
		x=x1;y=y1;
	}
	pFile=fopen("lacusta.out","w");
	fprintf(pFile,"%d",B[x][y]);
	return 0;
}

 Mitza444, on 5th September 2011, 11:38, said:

Unde ai judecat cazul cand  y == j  ? Da si acesta trebuie tratat
PS: Esti sigur ca-ti intra in ciclul infinit ?

Edited by secretalex92, 06 September 2011 - 08:05.

Mda ai avut dreptate a trebuit sa iau si cazul y==j

Dar am o alta intrebare la problema jucarii de pe .campion..

Eu m-am gandit asa sa fac un backtracking recursiv care imi genereaza toate solutiile in ordine lexicografica si la fiecare solutie pe care o gasesc sa fac verificarea daca are un subsir crescator de cel putin k elemente si de fiecare data cand gasesc un astfel de sir cresc o variabila care cand este egala cu p afisez solutia.
Problema e ca nu cred ca am facut bine functia care determina subsirul crescator + imi pica la timpul de executie la un test si la unul iau killed by signal 11 :|
Cum as puteam face determina subsirului in alt mod mai eficient??
Aici e codul:

#include<cstdio>
using namespace std;
int a[12],b[12],k,p,nr=0;
FILE * pFile;
void dinamic(int l){
	int s[13],j;
	s[1]=1;
	for(j=1;j<l;j++){
		if(a[j]<a[j+1]){
			s[j+1]=s[j]+1;
		}
	}
	if(s[l]>=k)nr++;
	pFile=fopen("jucarii.out","w");
	if(nr==p){
		for(j=1;j<=l;j++)
			fprintf(pFile,"%d ",a[j]);
	fprintf(pFile,"\n");
	}
}
void back(int x,int len){
	int i;
	if(x-1==len){
		dinamic(len);
	}
	else {
		for(i=1;i<=len;i++){
			if(!b[i]){
				a[x]=i;
				b[i]=1;
				back(x+1,len);
				b[i]=0;
			}
		}
	}
}
int main(){
	int n;
	pFile=fopen("jucarii.in","r");
	fscanf(pFile,"%d%d%d",&n,&k,&p);
	back(1,n);
	return 0;
}

Da, nu ai rezolvat bine dinamica. Uite un teste pe care ar pica

1 2 -1 -1 -1 3
Raspuns corect :   1 2 3

Vezi ca faci o confuzie intre subsecventa si subsir. Prima presupune ca elementele pe care le contine sa fie consecutive in sir, iar la subsir nu. Daca avem (xn), n natural nenul,  atunci un subsir este xi, xj, xk, ... cu conditia ca 0<i<j<k<... <=n => elementele unui subsir nu sunt neaparat consecutive.

1.Da ai avut dreptate nu era bine programarea dinamica am refacut-o si a mers....
2.La problema suma4 de pe .campion dupa ce determin numara de niveluri sa fac un for(i=1;i<=m;i++) si la fiecare pas sa pun nivelul respectiv in matrice(adica pun prima data 1 care are numai o casuta dupa pun nivelul 2 care are 4 casute si tot asa....) si la fiecare nivel sa adun minimum de pe nivelul anterior in cele 3 casute in care pot merge.Ar fi buna ideea??

 Mitza444, on 10th September 2011, 21:50, said:

Poti sa incerci si sa vezi . Dar, da e buna. Si sper ca atunci cand zici matrice te referi la una cu 3 dimensiuni.