Cod sursa(job #372031)

Utilizator dead_knightTitei Paul Adrian dead_knight Data 8 decembrie 2009 11:43:45
Problema Heapuri Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
/* Se dau n obiecte cu valoare si greutate cunoscuta.
se cunoasca greutatea max care poate fi carata.
Sa se aleaga obiecte a.i. valoarea totala sa fie maxima*/
#include<iostream>
#include<fstream>
using namespace std;
FILE * fin, * fout;
int v[100], c, n, g[100], p[100];

void read()
{
    fin=fopen("rucsac.in","r");
    fscanf(fin,"%d %d", &n, &c);
    int i;
    for(i=1;i<=n;i++)
    {
        fscanf(fin,"%d",&v[i]);
        p[i]=i;
    }
    for(i=1;i<=n;i++)
        fscanf(fin,"%d",&g[i]);
    fclose(fin);
}

int schimb(int i,int j)
{
    return v[p[i]]*g[p[j]]<g[p[i]]*v[p[j]];
}

void sort(int st, int dr)
{
    if(st<dr)
    {
        int d=(st+dr)/2, i=st, j=dr, aux;
        aux=p[d];
        p[d]=p[st];
        p[st]=aux;
        while(i<j)
        {
            if(schimb(i,j))
            {
                aux=p[i];
                p[i]=p[j];
                p[j]=p[i];
                d=1-d;
            }
            i+=d;
            j-=1-d;
        }
        sort(st,i-1);
        sort(i+1,dr);
    }
}

void write()
{
    fout=fopen("rucsac.out","w");
    int i,s;
    for(i=1,s=0;i<=n,s+g[i]<c;i++)
    {
        fprintf(fin,"%d",p[i]);
        s+=g[p[i]];
    }


    fclose(fout);
}

int main()
{
    read();
    sort(1,n);
    write();
    return 0;
}