Cod sursa(job #2148982)
Utilizator | Moldoveanu Cosmin Cosmin2004_Info | Data | 2 martie 2018 11:10:58 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.83 kb |
#include <cstdio>
using namespace std;
int v[10001],v2[10001];
void copyv(int g)
{
int i;
for(i=1;i<=g;i++)
{
v[i]=v2[i];
}
}
int main()
{
freopen("rucsac.in","r",stdin);
freopen("rucsac.out","w",stdout);
int n,g,w,p,i,j,pmax;
scanf("%d%d", &n,&g);
for(i=1;i<=g;i++)
{v[i]=-1;v2[i]=-1;}
for(i=1;i<=n;i++)
{
scanf("%d%d", &w,&p);
for(j=0;j<=g-1;j++)
{
if(v[j]!=-1)
{
if(j+w<=g)
{
if(v[j+w]<v[j]+p)
v2[j+w]=v[j]+p;
}
}
}
copyv(g);
}
pmax=0;
for(i=1;i<=g;i++)
{
if(pmax<v[i])
{
pmax=v[i];
}
}
printf("%d",pmax);
return 0;
}