Cod sursa(job #1804216)
Utilizator | Data | 12 noiembrie 2016 12:40:53 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.54 kb |
#include <cstdio>
#include <algorithm>
using namespace std;
const int G=10005;
int n,g,w,p,maxx,d[G];
int main()
{
freopen("rucsac.in","r",stdin);
freopen("rucsac.out","w",stdout);
scanf("%d%d",&n,&g);
for(int k=1;k<=n;k++){
scanf("%d%d",&w,&p);
if(w>g or p==0) continue;
for(int j=g-w;j>=0;j--)
if(d[j+w]<d[j]+p)
d[j+w]=d[j]+p;
}
for(int i=g;i>=0;i--)
if(d[i]>maxx)
maxx=d[i];
printf("%d\n",maxx);
return 0;
}