Cod sursa(job #1386343)

Utilizator StefanRARapeanu-Andreescu Stefan StefanRA Data 12 martie 2015 21:51:28
Problema Problema rucsacului Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.03 kb
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
    double c;
    double g;
} obiect;
int cmp_obiecte(const void *p, const void*q)
{
    obiect ob1=*(obiect *)p;
    obiect ob2=*(obiect *)q;
    if (ob1.c/ob1.g>ob2.c/ob2.g)
        return -1;
    if (ob1.c/ob1.g<ob2.c/ob2.g)
        return 1;
    return 0;
}
int main()
{
    int n, i;
    double k, ct;
    FILE *fp=fopen("rucsac.in", "r");
    fscanf(fp, "%d %lf", &n, &k);
    obiect *ob=(obiect *)malloc(n*sizeof(obiect));
    for (i=0;i<n;i++)
    {
        fscanf(fp, "%lf %lf", &ob[i].g, &ob[i].c);
    }
    fclose(fp);
    qsort(ob, n, sizeof(obiect), cmp_obiecte);
    fp=fopen("rucsac.out", "w");
    i=0;
    ct=0.0;
    while (i<n && k>0)
    {
        if (ob[i].g<=k)
        {
            ct=ct+ob[i].c;
            k=k-ob[i].g;
            i++;
        }
        else
        {
            ct=ct+ob[i].c*(k/ob[i].g);
            k=0;
        }
    }
    free(ob);
    fprintf(fp, "%.2f", ct);
    fclose(fp);
    return 0;
}