Cod sursa(job #650166)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 17 decembrie 2011 14:50:14
Problema Problema rucsacului Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.45 kb
#include <stdio.h>
int i , j , g ,  n, w , p , max=-1 , V[10001];
int main(){
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	scanf("%d%d",&n,&g);
	for(i=1;i<=n;i++){
		scanf("%d%d",&w,&p);
		for(j=g;j>=1;j--){
			if(V[j]!=0&&(j+w)<=g&&V[j+w]<(p+V[j])){
				V[j+w]=p+V[j];
				if(V[j+w]>max)
					max=V[j+w];
			}			
		}
		if(p>V[w]){
			V[w]=p;
			if(V[w]>max)
				max=V[w];
		}		
	}
	printf("%d",max);
	return 0;
}