Cod sursa(job #1312739)

Utilizator savigunFeleaga Dragos-George savigun Data 9 ianuarie 2015 21:29:29
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    int i, j, n, o[10001], aux, ct=0;
    float g[10001], c[10001], ef[10001], g1, aux1;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
    in>>n>>g1;

    for(i=1;i<=n;i++)
    {
        in>>g[i];
        in>>c[i];
        o[i]=i;
        ef[i]=c[i]/g[i];
    }

    for(i=1;i<=n-1;i++)
        for(j=i+1;j<=n;j++)
            if(ef[i]<ef[j])
            {
                aux=o[i];
                o[i]=o[j];
                o[j]=aux;
                aux1=ef[i];
                ef[i]=ef[j];
                ef[j]=aux1;
                aux1=c[i];
                c[i]=c[j];
                c[j]=aux1;
                aux1=g[i];
                g[i]=g[j];
                g[j]=aux1;
            }
    i=1;
    while(g1>0 && i<=n)
    {
        if(g[i]<=g1)
        {
            ct=ct+c[i];
            g1=g1-g[i];
            i++;
        }else
        {
        ct=ct + c[i]*g1/g[i];
        g1=0;
        }
    }

out<<ct;
    return 0;
}