Pagini recente » Cod sursa (job #1284505) | Cod sursa (job #1318313) | Cod sursa (job #1437014) | Cod sursa (job #1838773) | Cod sursa (job #1125806)
#include <iostream>
#include <fstream>
using namespace std;
int n,g,v[5000],w[5000],s[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];
s[i]=i;
}
for(int i=0;i<n;i++)
ef[i] = v[i]/w[i];
bool z;
do
{
z=false;
for(int i=1;i<n;i++)
if(ef[s[i-1]]<ef[s[i]])
{
z=true;
int aux = s[i-1];
s[i-1] = s[i];
s[i] = aux;
}
}
while(z);
}
int main()
{
citire();
for(int i=0;i<n && g>0;i++)
if (g>=w[s[i]])
{
g-=w[s[i]];
t+=v[s[i]];
}
else
{
t+=ef[s[i]]*g;
g=0;
}
gout<<t;
return 0;
}