Pagini recente » Cod sursa (job #2393078) | Cod sursa (job #3224746) | Cod sursa (job #1301) | Cod sursa (job #876763) | Cod sursa (job #1942641)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
double p[5005],g[5005],n,s,G,rez,schimb,rap[5005],st,dr;
int main() {
fin>>n>>G;
for(int i=1;i<=n;i++)
{
fin>>g[i]>>p[i];
rap[i]=p[i]/g[i];
}
do
{
schimb=0;
for(int i=n-1;i>=1;i--)
{
if(rap[i]<rap[i+1])
{swap(rap[i],rap[i+1]);
swap(p[i],p[i+1]);
swap(g[i],g[i+1]);
schimb=1;
}
else
if(rap[i]==rap[i+1])
{
if(p[i]<p[i+1])
{swap(rap[i],rap[i+1]);
swap(p[i],p[i+1]);
swap(g[i],g[i+1]);
schimb=1;
}
}
}
}
while(schimb);
int i=1;
while(s+g[i]<=G)
{
s=s+g[i];
rez=rez+p[i];
i++;
}
if (rez-p[i-1]+p[i]>rez && s-g[i-1]+g[i]<=G)
rez=rez-p[i-1]+p[i];
fout<<rez;
return 0;
}