Cod sursa(job #687226)

Utilizator HoriaClementHoriaC HoriaClement Data 22 februarie 2012 10:55:53
Problema Energii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>

using namespace std;

const int inf=0x3FFFFFFF;//infinit pt min

int n,cost[1005][5005],g;

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

struct knap
{
	int e,c;
};
knap v[1005];

inline int minim(int x,int y)
{
	return x < y ? x : y;
}

void citire()
{
	in>>n>>g;
	for(int i=1;i<=n;++i)
		in>>v[i].e>>v[i].c;
	for(int i=0;i<=n;++i)
		for(int j=1;j<=g;++j)
			cost[i][j]=inf;
	
}

void rucsac()
{
	for(int i=1;i<=n;++i)
		for(int j=1;j<=g;++j)
			if(v[i].e<=j)
				cost[i][j]=minim(cost[i-1][j],cost[i-1][j-v[i].e]+v[i].c);
			else
				cost[i][j]=minim(cost[i-1][j],v[i].c);
	if(cost[n][g]==inf)
		cost[n][g]=-1;
	out<<cost[n][g];
}

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