Cod sursa(job #820616)
Utilizator | Data | 21 noiembrie 2012 08:14:00 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 50 |
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 p[100001],g[100001],prf[1001],k,n;
int main()
{
in>>n>>k;
for(int i=1;i<=n;i++)
in>>g[i]>>p[i];
for(int i=1;i<=n;i++)
prf[i]=-1;
prf[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=k-g[i];j>=0;j--)
if(prf[j]!=-1 && prf[j]+p[i]>prf[j+g[i]])
prf[j+g[i]]=p[i]+prf[j];
}
int max=1;
for(int j=1;j<=k;j++)
if(prf[j]>max)
max=prf[j];
out<<max;
return 0;
}