Pagini recente » Monitorul de evaluare | Cod sursa (job #1839151) | Cod sursa (job #1838182) | Cod sursa (job #505833) | Cod sursa (job #1125828)
#include <iostream>
#include <fstream>
using namespace std;
int n,g,v[5000],w[5000];
float t,ef[5000];
ifstream f("rucsac.in");
ofstream gout("rucsac.out");
void citire()
{
f>>n>>g;
t=0;
for(int i=0;i<n;i++)
{
f>>w[i]>>v[i];
ef[i] = v[i]/w[i];
}
bool z;
do
{
z=false;
for(int i=1;i<n;i++)
if(ef[i-1]<ef[i])
{
z=true;
float aux = ef[i];
ef[i] = ef[i-1];
ef[i-1] = aux;
aux = w[i];
w[i] = w[i-1];
w[i-1] = aux;
aux = v[i];
v[i] = v[i-1];
v[i-1] = aux;
}
}
while(z);
}
int main()
{
citire();
for(int i=0;i<n && g>0;i++)
if (g>=w[i])
{
g-=w[i];
t+=v[i];
}
else
{
t+=v[i]/w[i]*g;
g=0;
}
cout<<t;
return 0;
}