Cod sursa(job #1905830)

Utilizator andreigeorge08Sandu Ciorba andreigeorge08 Data 6 martie 2017 11:10:56
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <bits/stdc++.h>

using namespace std;
int g[10005],v[10005],n,G;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
void Citire()
{
    fin>>n>>G;
    for(int i=1;i<=n;i++)
        fin>>g[i]>>v[i];
}
void Rez()
{
    double smax=0;
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            if(v[i]*g[j]<v[j]*g[i])
            {
                swap(v[i],v[j]);
                swap(g[i],g[j]);
            }
    int i=1;
    while(i<=n && G>=g[i])
    {
        G-=g[i];
        smax+=v[i];
        i++;
    }
    if(i<=n)
        smax+=(G*v[i]/g[i]);
    fout<<smax<<"\n";
}
int main()
{
    Citire();
    Rez();
    return 0;
}