Pagini recente » Monitorul de evaluare | Cod sursa (job #279892) | Cod sursa (job #1777804) | Cod sursa (job #887314) | Cod sursa (job #1006868)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
typedef struct{
int indice;
int gr;
int val;
float rap;
}obiect;
vector<obiect> v;
bool compare (obiect a, obiect b)
{
if(a.rap>b.rap)
return 0;
else
return 1;
}
int main()
{
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, G, i;
float max_val=0;;
fin>>n>>G;
for(i=0;i<n;i++)
{
obiect aux;
fin>>aux.gr>>aux.val;
aux.indice=i+1;
aux.rap=(1.0*aux.val)/aux.gr;
v.push_back(aux);
}
//fout<<"obiectele alese sunt:\n";
make_heap(v.begin(),v.end(),compare);
for( i=0; i<n && G-v.front().gr>=0; i++)
{
//fout<<v.front().indice<<" ("<<v.front().gr<<" "<<v.front().val<<")"<<"\n";
G-=v.front().gr;
max_val+=v.front().val;
pop_heap(v.begin(),v.end(),compare);
v.pop_back();
}
//fout<<G*100/v.front().gr<<"% "<<v.front().indice<<" ("<<v.front().gr<<" "<<v.front().val<<")";
//max_val+=(G*1.0)/v.front().gr*v.front().val;
fout/*<<"\nValoarea maxima admisa: "*/<<max_val;
return 0;
}