Cod sursa(job #2754537)

Utilizator danibaciuBaciu Daniel Mihai danibaciu Data 25 mai 2021 23:30:04
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
using namespace std;

istream fin("rucsac.in");
ofstream fout("rucsac.out");
struct hot
{int g,val;float r;};
void citire(hot v[],int &n,int &G)
{
    int i;
    fin>>n>>G;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].g>>v[i].val;
        v[i].r=(float)v[i].val/v[i].g;
    }
}
void ordo(hot v[],int n)
{
    int i,ok;
    do
    {
        ok=0;
        for(i=1;i<=n;i++)
        {
            if(v[i].r<v[i+1].r)
            {
                v[0]=v[i];
                v[i]=v[i+1];
                v[i+1]=v[0];
                ok=1;
            }
        }
    }while(ok==1);
}
void gridi(hot v[],int n,int G)
{
    int i;float VAL=0;
    for(i=1;i<=n&&G>0;i++)
    {
        if(v[i].g<=G)
        {
            G-=v[i].g;
            VAL+=v[i].val;
        }
        else
        {
            VAL+=G*v[i].r;
            G=0;
        }
    }
    fout<<VAL;
}
int main()
{
    int n,G;hot v[5001];
    citire(v,n,G);
    ordo(v,n);
    gridi(v,n,G);
    return 0;
}