Cod sursa(job #1006868)

Utilizator costel93FMI - Dumea Eduard Constantin costel93 Data 7 octombrie 2013 20:56:32
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#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;
}