Pagini recente » Borderou de evaluare (job #2697272) | Cod sursa (job #2037601)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,G,costmax,cost,greu;
short x[10001],y[10001];
struct obiect
{
int g,c;
}v[100];
void verif()
{
cost=0;
for(int i=1;i<=n;i++)
cost=cost+x[i]*v[i].c;
if(cost>costmax)
{
costmax=cost;
for(int j=1;j<=n;j++)
y[j]=x[j];
}
}
void read()
{
fin>>n>>G;
for(int i=1;i<=n;i++)
fin>>v[i].g>>v[i].c;
}
void back(int k)
{
if(k>n)
verif();
else
{
x[k]=1;
greu=greu+v[k].g;
if(greu<=G)
back(k+1);
greu=greu-v[k].g;
x[k]=0;
back(k+1);
}
}
int main()
{
int cmax=0;
read();
back(1);
for(int i=1;i<=n;i++)
if(y[i]==1)
cmax=cmax+v[i].c;
fout<<cmax<<'\n';
/*for(int i=1;i<=n;i++)
if(y[i]==1)
fout<<v[i].c<<" ";*/
return 0;
}