Cod sursa(job #697225)

Utilizator HoriaClementHoriaC HoriaClement Data 28 februarie 2012 23:14:54
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.48 kb
#include <fstream>

using namespace std;

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

int n,s,g[10005],p[10005],v[10005];

const int inf=-10000000;

inline int maxim(int x,int y)
{
	return x > y ? x : y;
}

void citire()
{
	in>>n>>s;
	for(int i=1;i<=n;++i)
		in>>g[i]>>p[i];
	for(int i=1;i<=s;++i)
		v[i]=inf;
	v[0]=0;
	for(int i=1;i<=n;++i)
		for(int j=s-g[i];j>=0;--j)
			if(v[j]!=inf)
				v[j+g[i]]=max(v[j+g[i]],v[j]+p[i]);
	out<<v[s];
}
	

int main()
{
	citire();
	return 0;
}