Cod sursa(job #1942641)

Utilizator aturcsaTurcsa Alexandru aturcsa Data 28 martie 2017 09:35:51
Problema Problema rucsacului Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

double p[5005],g[5005],n,s,G,rez,schimb,rap[5005],st,dr;
int main() {
    fin>>n>>G;
    for(int i=1;i<=n;i++)
    {
        fin>>g[i]>>p[i];
        rap[i]=p[i]/g[i];
    }
    do
    {
        schimb=0;
            for(int i=n-1;i>=1;i--)
            {
                if(rap[i]<rap[i+1])
                    {swap(rap[i],rap[i+1]);
                    swap(p[i],p[i+1]);
                    swap(g[i],g[i+1]);
                    schimb=1;
                    }
                else
                if(rap[i]==rap[i+1])
                {
                	if(p[i]<p[i+1])
                    {swap(rap[i],rap[i+1]);
                    swap(p[i],p[i+1]);
                    swap(g[i],g[i+1]);
                    schimb=1;
                    }
                }
            }
    }
    while(schimb);

    int i=1;
    while(s+g[i]<=G)
    {
        s=s+g[i];
        rez=rez+p[i];
        i++;
    }
    if (rez-p[i-1]+p[i]>rez && s-g[i-1]+g[i]<=G)
    	rez=rez-p[i-1]+p[i];
    fout<<rez;
    return 0;
}