Cod sursa(job #1973675)

Utilizator radumihaisirbuSirbu Radu-Mihai radumihaisirbu Data 25 aprilie 2017 18:09:54
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <cmath>
#include <fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
struct rucsac
{
    int c,g;
    float ef;
}v[5001];
int n,gmax,i,j,G=0;
float cmax;
int main()
{
    fin>>n>>gmax;
    for (i=1;i<=n;i++)
        {fin>>v[i].g>>v[i].c;

   v[i].ef=(float)v[i].g/v[i].c;}
    for (i=1;i<n;i++)
       for (j=i+1;j<=n;j++)
    {
        if (v[j].ef>v[i].ef)
         swap (v[i],v[j]);
        else if (fabs(v[j].ef-v[i].ef)<0.01)
            if (v[j].c>v[i].c)
                swap (v[i],v[j]);


    }
    for (i=n;i>=1;i--)
    {
       if (G+v[i].g>gmax)
        {
         cmax=cmax+(float)(gmax-G)/v[i].ef;
         break;
        }
    else {cmax=cmax+v[i].c; G=G+v[i].g;}
    }
    fout<<cmax;
    fout.close();
    return 0;
}