Cod sursa(job #2421683)

Utilizator PopescuLucianPopescu Lucian PopescuLucian Data 15 mai 2019 19:16:59
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
struct obiect
{
    int V,G;
    float estimare;
};
    obiect a[1200];
    int n,i,gmax,j;
    float s=0,smax=0;
    int main()
{
    fin>>n>>gmax;
    for(i=1;i<=n;i++)
    {
        fin>>a[i].G>>a[i].V;
        a[i].estimare= (float) a[i].V / a[i].G;
    }
    for(i=1;i<=n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            if(a[i].estimare<a[j].estimare)
            {
                swap(a[i].estimare,a[j].estimare);
                swap(a[i].G,a[j].G);
                swap(a[i].V,a[j].V);
            }
        }
    }
    i=1;
    while(gmax>0 && i<=n)
        {
            if(gmax-a[i].G>=0)
            {
                gmax=gmax-a[i].G;
                s=s+a[i].V;
            }
            else
                if(gmax-a[i].G<0)
            {
                s=s + gmax*a[i].estimare;
                gmax=0;
            }
           if(s>smax)
          {
               smax=s;
            }
           i++;
        }
        fout<<s;
        return 0;

}