Pagini recente » Borderou de evaluare (job #1388479) | Borderou de evaluare (job #1388470) | Cod sursa (job #1174189)
#include<fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int W[10001],P[10001],sol[2][10001],G,N,i,j,l;
int main()
{
in>>N>>G;
for(i = 1 ; i <= N ; i++)
in>>W[i]>>P[i];
for(i = 1 ; i <= G ; i++)
{
l = 1-l;
for(j = 0 ; j <= G ; j++)
{
sol[1-l][j] = sol[l][j];
if(W[i] <= j)
sol[1-l][j] = max(sol[1-l][j],sol[l][j-W[i]]+P[i]);
}
}
out<<sol[l][G];
return 0;
}