Cod sursa(job #2397096)

Utilizator BigBoss_29Matei Cristian BigBoss_29 Data 4 aprilie 2019 10:27:30
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
using namespace std;

int x,z,y,i,j,n,g,a[100],c[100];
double b[100];
int s=0;
int v=0;
    ifstream cin("rucsac.in");
	ofstream cout("rucsac.out");
int main(){
 //cout<<" dati nr. de pietre ->  ";
 cin>>n>>g;
 //cout<<" Dati volumul ruxacului -> ";
 //cin>>g;

for (i=1; i<=n; i++) {
cin>>a[i]>>c[i];
//cout<<" Masa  ["<<i<<"] -> "; cin>>a[i];

//cout<<" Costul  ["<<i<<"] -> "; cin>>c[i];

b[i]=c[i]/a[i];}

//for (i=1; i<=n; i++){
//	cout<<b[i]<<" ";
//
//}
//cout<<endl;

for (i=1; i<=n; i++){
	for (j=i+1; j<=n; j++){
		if(b[j]>b[i]){
			x=b[i];
			b[i]=b[j];
			b[j]=x;
			   y=a[i];
			   a[i]=a[j];
			   a[j]=y;
			   	  z=c[i];
		         	c[i]=c[j];
		            	c[j]=z;
		}
	}

}

//for (i=1; i<=n; i++){
//cout<<b[i]<<" ";
//}
//cout<<endl;
i=1;
while(s!=g){
	if ((s+a[i])>g){
		if (s==0){//cout<<" Nu au fost puse in rucsac pietre intregi"<<endl;
		//cout<<" Masa bucatita -> "<<g<<endl;
		v=v+(g-s)*b[i];
		s=g;
		}
		else{


		//cout<<" Greutate si costul pietrelor intregi "<<s<<" "<<v<<endl;
		//cout<<" Masa bucatita "<<g<<endl;
		v=v+(g-s)*b[i];
		s=g;}




	}
	else{s=s+a[i];
	v=v+c[i];
	i++;
	}
}

	//cout<<" Costul maxim: "<<v;
	cout<<v;





	return 0;
}