Cod sursa(job #1616220)
| Utilizator | Data | 27 februarie 2016 10:40:09 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.66 kb |
#include <iostream>
#include <cstdio>
using namespace std;
int a[10010],w[5010],p[5010];
int n,g;
int main()
{
freopen("rucsac.in","r",stdin);
freopen("rucsac.out","w",stdout);
scanf("%d %d",&n,&g);
for(int i=1;i<=n;i++)
scanf("%d %d",&w[i],&p[i]);
a[w[1]]=p[1];
for(int i=2;i<=n;i++)
for(int j=g;j>0;j--)
if(j-w[i]>=0)
if(j==w[i])
a[j]=max(a[j],p[i]);
else if(a[j-w[i]])
a[j]=max(a[j],a[j-w[i]]+p[i]);
int maxi=-1;
for(int i=1;i<=g;i++)
maxi=max(maxi,a[i]);
printf("%d",maxi);
return 0;
}
