Cod sursa(job #2065507)

Utilizator armand200Armand Cismaru armand200 Data 13 noiembrie 2017 20:44:26
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ("ruscac.in");
ofstream g ("rucsac.out");
int n,Gm;
double prM;
struct nod
{
    int gr;
    int val;
    double pr;
} a[1005];

bool cmp (nod x, nod y)
{
    if(x.pr>y.pr) return true;
    else
        return false;
}

void load ()
{
    f>>n>>Gm;
    for( int i=1; i<=n; i++ )
    {
        f>>a[i].gr>>a[i].val;
        a[i].pr=(double)a[i].val/a[i].gr;
    }
}

int main ()
{
    int k=0,nr=0;

    load ();
    sort (a+1,a+n+1,cmp);

    for(int i=1; i<=n; i++)
    {
        if(a[i].gr+k<=Gm)
        {
            prM+=a[i].val;
            k+=a[i].gr;
        }
        else if(a[i].gr+k>Gm)
        {
            nr=Gm-k;
            prM+=nr*a[i].pr;
            break;
        }

    }
    g<<prM;
     return 0;
}