Cod sursa(job #1707197)

Utilizator SabjayProdan Alexandru Sabjay Data 24 mai 2016 16:30:23
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
#include<algorithm>

using namespace std;

ifstream fi("rucsac.in");
ofstream fo("rucsac.out");

int N,G,n[10000],g[10000],f,S;
double val[10000];

int main()
{
	fi>>N>>G;
	for(int i=1;i<=N;i++) {
							fi>>g[i]>>n[i];
							val[i]=(n[i]*1.0)/(g[i]*1.0);
							}
	for(int i=1;i<=N;i++) for(int j=i;j<=N;j++) {
													if(val[i]<val[j]){
																		swap(val[i],val[j]);
																		swap(n[i],n[j]);
																		swap(g[i],g[j]);
																		}
														}
	//for(int i=1;i<=N;i++) fo<<val[i]<<" "<<n[i]<<" "<<g[i]<<endl;
	while(G!=0){
				f++;
				if(G-g[f]>=0) {
								S+=n[f];
								G-=g[f];
								}
				else {
						S+=(G)*val[f];
						G=0;
						}
				}
	fo<<S;
}