Pagini recente » Cod sursa (job #1065275) | Cod sursa (job #1797960) | Cod sursa (job #1146616) | Cod sursa (job #1496384) | Cod sursa (job #2047720)
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,G,i,j,ma,gr[5001],p[5001],b[10001];
int main()
{f>>n>>G;
for(i=1;i<=n;++i)
f>>gr[i]>>p[i];
b[gr[1]]=p[1];
for(i=2;i<=n;++i)
{ for(j=G-gr[i];j>=1;--j)
if(b[j]>0)
if(b[j+gr[i]]<b[j]+p[i])
b[j+gr[i]]=b[j]+p[i];
if(b[gr[i]]<p[i])
b[gr[i]]=p[i];}
ma=0;
for(i=G;i>=1;--i)
if(b[i]>ma)
ma=b[i];
g<<ma<<'\n';
return 0;
}