Pagini recente » Borderou de evaluare (job #2265199) | Borderou de evaluare (job #2775112) | Cod sursa (job #2293844) | Cod sursa (job #2428175)
#include <fstream>
using namespace std;
ifstream in ("rucsac.in");
ofstream out ("rucsac.out");
const int NMAX = 5000;
const int GMAX = 10001;
int w[NMAX], p[NMAX], profit[GMAX];
int main()
{
int n, g, i, j, maxim=-2;
in>>n>>g;
for(j=1; j<=g; j++)
profit[j]=-1;
profit[0]=0;
for(i=0; i<n; i++)
{
in>>w[i]>>p[i];
}
for(i=0; i<n; i++)
{
for(j=g-w[i]; j>=0; j--)
{
if(profit[j]!=-1 && profit[j]+p[i]>profit[j+w[i]])
{
profit[j+w[i]]=profit[j]+p[i];
}
}
}
for(j=1; j<=g; j++)
{
if(profit[j]>maxim)
maxim=profit[j];
}
out<<maxim;
in.close();
out.close();
return 0;
}