Cod sursa(job #1431278)
Utilizator | Draghici Bogdan bogdan14 | Data | 9 mai 2015 10:01:55 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream k("rucsac.out");
int N,G,s[10001],i,j,mx,g,p;
int main()
{
mx=0;
f>>N>>G;
for(i=1;i<=G;i++)
s[i]=-1;
s[0]=0;
for(i=1;i<=N;i++)
{
f>>g>>p;
for(j=G-g;j>=0;j--)
if(s[j]!=-1)
if(s[j+g]<s[j]+p)
s[j+g]=s[j]+p;
}
for(i=1;i<=G;i++)
if(s[i]>mx)
mx=s[i];
k<<mx;
f.close();
k.close();
return 0;
}