Cod sursa(job #1579810)

Utilizator ioanalexandraIoan Alexandra ioanalexandra Data 25 ianuarie 2016 09:04:06
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <stdio.h>
#include <algorithm>
#include <cmath>
FILE*f=fopen("rucsac.in","r");
FILE*h=fopen("rucsac.out","w");
using namespace std;

struct ob
{
    int c,g;
    int o;
}a[50001];
int gmax,ct,gm;
int n;
int comp(ob a, ob b)
{
    if (fabs((float)a.c/a.g-(float)b.c/b.g)<0.0001) return a.g<b.g;
    else return (float)a.c/a.g-(float)b.c/b.g>0.0001;
}
void citire()
{
    int i;
    fscanf(f,"%d%d",&n,&gm);
    for (i=1;i<=n;i++) fscanf(f,"%d%d",&a[i].g,&a[i].c);
}
int main()
{
    int i;
    citire();
    sort(a+1,a+n+1,comp);
    ct=0;
    i=1;
    while(gm>0 && i<=n)
    {
        if(a[i].g<gm)
        {
          gm-=a[i].g;
          ct+=a[i].c;
        }
        else { if (a[i].g==gm){
        ct+=a[i].c;
        gm=0;}
    }i++;
    }
    fprintf(h,"%d",ct);
    return 0;
}