Cod sursa(job #1002380)
Utilizator | Alexa Tudose Alexa2001 | Data | 27 septembrie 2013 17:34:54 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 65 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int j,i,gmax,gg,n,p,Max;
long long a[50003];
int main()
{
f>>n>>gmax>>gg>>p;
if(gg<=10000) a[gg]=p;
for(j=1;j<n;++j)
{f>>gg>>p;
for(i=5000;i>=0;--i) if(a[i]>0 && i+gg<=10000) {if(a[i+gg]==0)a[i+gg]=a[i]+p;else if(a[i+gg]<a[i]+p) a[i+gg]=a[i]+p;};
if( a[gg]==0) a[gg]=p;
else if(a[gg]<p) a[gg]=p;
}
Max=0;
for(i=0;i<=gmax;++i) if(Max<a[i]) Max=a[i];
g<<Max<<'\n';
return 0;
}