Pagini recente » Cod sursa (job #2681730) | Cod sursa (job #2810746) | Cod sursa (job #3292579) | Cod sursa (job #2500596) | Cod sursa (job #1937900)
#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() {
cin>>n>>G;
for(int i=1;i<=n;i++)
{
cin>>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;
}
}
}
while(schimb);
// st=rap[1];
// dr=st;
// for(int i=2;i<=n;i++)
// {
// if(rap[i]==st){dr++;cout<<"!";}
// if(rap[i]!=st){sort(p+1+st,p+1+dr);sort(g+1+st,g+1+dr);st=dr;cout<<"?";}
// }
for(int i=1;i<=n;i++)
cout<<g[i]<<" "<<p[i]<<" ("<<rap[i]<<")\n";
int i=1;
while(s+g[i]<=G)
{
s=s+g[i];
rez=rez+p[i];
i++;
// cout<<p[i]<<" ";
}
cout<<rez;
return 0;
}