Cod sursa(job #902409)
Utilizator | Ionut Calofir Ionut228 | Data | 1 martie 2013 14:04:00 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.65 kb |
#include<fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
#define nmax 5002
#define gmax 10002
int w[nmax],p[nmax],best[gmax],n,gr,sol;
int main ()
{
f>>n;
f>>gr;
for(int i=1;i<=n;i++)
{
f>>w[i];
f>>p[i];
}
best[0]=0;
sol=0;
for(int i=1;i<=n;i++)
for(int j=gr-w[i];j>=0;j--)
{
if(best[j+w[i]]<best[j]+p[i])
{
best[j+w[i]]=best[j]+p[i];
if(best[j+w[i]]>sol)
sol=best[j+w[i]];
}
}
g<<sol;
f.close();g.close();
return 0;
}