Cod sursa(job #3234629)

Utilizator alexxiacrisanCrisan Maria - Alexia alexxiacrisan Data 10 iunie 2024 19:23:21
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, gm;
int castig = 0;

struct obiect 
{
    int g, v;
} o[5001]; 

void citire() 
{
    fin >> n >> gm;
    for(int i = 1; i <= n; i++) 
        fin >> o[i].g >> o[i].v;
}

void sortare() 
{
  
    sort(o + 1, o + n + 1, [](obiect a, obiect b) 
    {
        return a.v * b.g > b.v * a.g;
    });
}

int alegere() 
{
    for(int i = 1; i <= n && gm != 0; i++) 
    {
        if(o[i].g <= gm) 
        {
            gm -= o[i].g;
            castig += o[i].v;
        } 
        else 
        {
            castig += (float)o[i].v / o[i].g * gm;
            gm = 0;
        }
    }
    return castig;
}

int main() {
    citire();
    sortare();
    fout << alegere() << "\n";
    fin.close();
    fout.close();
    return 0;
}