Cod sursa(job #642529)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 1 decembrie 2011 16:38:17
Problema Problema rucsacului Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");

const int N=5011;
const int G=10011;

struct obiect{
	int g,p;
}v[N];

int n,greu;
int rez[G];

int main(){
	int i,j;
	in>>n>>greu;
	for(i=1;i<=n;++i){
		in>>v[i].g>>v[i].p;
	}
	for(i=1;i<=n;++i){
		for(j=greu;j>=0;--j){
			if(rez[j] && v[i].p+rez[j]>rez[j+v[i].g] && (j+v[i].g)<=greu ){
				rez[j+v[i].g]=v[i].p+rez[j];
			}
		}
		if(rez[v[i].g]<v[i].p){
			rez[v[i].g]=v[i].p;
		}
	}
	int maxim=0;
	for(i=0;i<=greu;++i)
		if(rez[i]>maxim)
			maxim=rez[i];
	out<<maxim;
	return 0;
}