Mai intai trebuie sa te autentifici.
Cod sursa(job #1614869)
Utilizator | Grama Matei daGrama | Data | 26 februarie 2016 11:15:07 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.73 kb |
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
struct obj{double p,g,rap;}o[5005];
int n,k;
int d[10000][5005];
inline bool cmp(obj x,obj y){
return x.rap<y.rap;
}
void cit(){
f>>n>>k;
for(int i=1;i<=n;i++){
f>>o[i].g>>o[i].p;
o[i].rap=o[i].g/o[i].p;
}
}
int main()
{
cit();
sort(o+1,o+n+1,cmp);
bool ok = true;
int i=1, pr=0;
while(ok){
if(k<o[i].g){
ok=false;
}
else{
k-=o[i].g;
pr+=o[i].p;
i++;
}
}
g<<pr;
/*
for(int i=1;i<=n;i++)
g<<o[i].p<<" "<<o[i].g<<" "<<o[i].rap<<'\n';
*/
return 0;
}