Cod sursa(job #1125828)

Utilizator bflorin97Bardas Florin bflorin97 Data 26 februarie 2014 19:42:44
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>

using namespace std;

int n,g,v[5000],w[5000];
float t,ef[5000];
ifstream f("rucsac.in");
ofstream gout("rucsac.out");

void citire()
{
    f>>n>>g;
    t=0;
    for(int i=0;i<n;i++)
    {
        f>>w[i]>>v[i];
        ef[i] = v[i]/w[i];
    }
    bool z;
    do
    {
        z=false;
        for(int i=1;i<n;i++)
            if(ef[i-1]<ef[i])
            {
                z=true;
                float aux = ef[i];
                ef[i] = ef[i-1];
                ef[i-1] = aux;

                aux = w[i];
                w[i] = w[i-1];
                w[i-1] = aux;

                aux = v[i];
                v[i] = v[i-1];
                v[i-1] = aux;
            }
    }
    while(z);
}

int main()
{
    citire();
    for(int i=0;i<n && g>0;i++)
        if (g>=w[i])
        {
            g-=w[i];
            t+=v[i];
        }
        else
        {
            t+=v[i]/w[i]*g;
            g=0;
        }
    cout<<t;
    return 0;
}