Cod sursa(job #2929273)

Utilizator PingStrpewpewpac PingStr Data 25 octombrie 2022 14:17:46
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int a[7001], b[7001], n, gmax;
float c[7001];

int greedy();
int maxx();

int main()
{
    fin>>n>>gmax;
    for (int i = 1; i <= n; i++)
    {
        fin>>a[i]>>b[i];
    }
    for (int i = 1; i <= n; i++)
    {
        c[i] = (float)b[i] / a[i];
    }
    fout<<greedy();
    return 0;
}

int greedy()
{
    int profit = 0, k;
    while(gmax)
    {
        k = maxx();
        if (a[k] > gmax)
        {
            profit = profit + (gmax * b[k]) / a[k];
            gmax = 0;
        }
        else
        {
            profit = profit + b[k];
            gmax = gmax - a[k];
        }
        c[k] = 0;
    }
    return profit;
}

int maxx()
{
    float max = c[1];
    int k = 1;
    for (int i = 2; i <= n; i++)
    {
        if (max < c[i])
        {
            max = c[i];
            k = i;
        }
    }
    return k;
}