Pagini recente » Borderou de evaluare (job #1373340) | Cod sursa (job #3205661)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
#define maxn 5001
#define maxg 10001
int N, G, W[maxn], P[maxn], O[maxg], i, j, sol;
int main()
{
fin>>N>>G;
for(i=1;i<=N;i++)
{
fin>>W[i]>>P[i];
}
O[0]=0;
sol=0;
for(i=1;i<=N;i++)
{
for(j=G-W[i];j>=0;j--)
{
if(O[j+W[i]]<O[j]+P[i])
{
O[j+W[i]]=O[j]+P[i];
}
if(O[j+W[i]]>sol)
{
sol=O[j+W[i]];
}
}
}
fout<<sol;
return 0;
}