Cod sursa(job #1844744)

Utilizator cochinteleandreeaCochintele Andreea Elena cochinteleandreea Data 10 ianuarie 2017 13:45:22
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>
using namespace std;
int n,gmax,i,s,in,x[5005];
double c[5005];
bool ok;
struct nod
{
    double cost;
    int ind;
}c1[5005],aux;
int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    f>>n>>gmax;
    for(i=1;i<=n;i++)
    {
       f>>x[i]>>c[i];
        c1[i].cost=c[i]/x[i];
        c1[i].ind=x[i];
    }
    do
    {
        ok=true;
        for(i=1;i<n;i++)
        if(c1[i].cost<c1[i+1].cost)
        {aux=c1[i];c1[i]=c1[i+1];c1[i+1]=aux;ok=false;}
    }while(!ok);

    for(i=1;i<=n;i++)
    if(in+c1[i].ind<gmax ) {in+=c1[i].ind;  s+=c1[i].ind*c1[i].cost;}
    else s+= c1[i].cost*(gmax-in),in=gmax;

    g<<s;
    return 0;
}