Cod sursa(job #1182981)
| Utilizator | Data | 8 mai 2014 11:30:36 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.53 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
struct rap
{
short p,v;
};
bool cmp(rap p,rap q)
{
if(p.p*q.v>p.v*q.p) return 1;
return 0;
}
int main()
{
short n,g,i,vo=0;
int s=0;
rap v[5001];
f>>n>>g;
for(i=1;i<=n;i++)
f>>v[i].v>>v[i].p;
sort(v+1,v+n+1,cmp);
i=1;
while(vo+v[i].v<=g&&i<=n)
{
s+=v[i].p;
vo+=v[i].v;
i++;
}
g<<s;
return 0;
}
