Cod sursa(job #2053206)

Utilizator munteanubodiMunteanu Cosmin-Bogdan munteanubodi Data 31 octombrie 2017 16:57:48
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
using namespace std;
struct ob{int nr, val,g;
          float ef;}v[1001],x[1001];
int n,m,G;
float t;
void citire(ob v[],int &n)
{
    cin>>n>>G;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].g>>v[i].val;
        v[i].nr=i;
        v[i].ef=(float) v[i].val/v[i].g;
    }
}
void ord()
{
    for(int i=1;i<n;i++)
        for(int j=i;j<=n;j++)
        if(v[i].ef<v[j].ef)
    {
        ob aux=v[i];
        v[i]=v[j];
        v[j]=aux;
    }
}
void greedy()
{
    t=0;
    int i=1;
    while(i<=n&&G!=0)
    {
        if(v[i].g<=G)
        {
            t=t+v[i].val;
            G-=v[i].g;

        }
        else {t=t+G*v[i].ef;G=0;}
        i++;
    }
}
int main()
{
    citire (v,n);
    ord();
    greedy();
    cout<<t;
    return 0;
}