Cod sursa(job #1937900)

Utilizator aturcsaTurcsa Alexandru aturcsa Data 24 martie 2017 13:12:55
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 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() {
	cin>>n>>G;
	for(int i=1;i<=n;i++)
	{
		cin>>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;
					}
			}
	}
	while(schimb);
//	st=rap[1];
//	dr=st;
//	for(int i=2;i<=n;i++)
//	{
//		if(rap[i]==st){dr++;cout<<"!";}
//		if(rap[i]!=st){sort(p+1+st,p+1+dr);sort(g+1+st,g+1+dr);st=dr;cout<<"?";}
//	}
	for(int i=1;i<=n;i++)
		cout<<g[i]<<" "<<p[i]<<" ("<<rap[i]<<")\n";
	int i=1;
	while(s+g[i]<=G)
	{
		s=s+g[i];
		rez=rez+p[i];
		i++;
//		cout<<p[i]<<" ";
	} 
	cout<<rez;
	return 0;
}