Cod sursa(job #697225)
Utilizator | HoriaC 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;
}