Cod sursa(job #3288141)

Utilizator Op_IanisOpritescu Ianis Op_Ianis Data 20 martie 2025 18:09:33
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
// Fractional Knapsack Problem - Greedy
// Time: O(n * logn)
// Space: O(n)
#include <fstream>
#include <vector>
#include <algorithm>

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

void solve(std::vector<std::pair<int,int>>& objs, int& N, int& G) {
    std::sort(objs.begin(), objs.end(), [](const std::pair<int,int>& a, const std::pair<int,int>& b) {
        return a.second * 1.0 / a.first > b.second * 1.0 / b.first;
    });

    int winnings = 0;
    for (auto & item : objs) {
        if (item.first <= G) {
            winnings += item.second;
            G -= item.first;
        } else {
            winnings += item.second * 1.0/ item.first * G;
            break;
        }
    }

    fout << winnings << "\n";
}

void readInput(std::vector<std::pair<int,int>>& arr, int &N, int &G) {
    fin >> N >> G;
    for (int i = 0; i < N; i++) {
        int x, y;
        fin >> x >> y;
        arr.push_back(std::make_pair(x,y));
    }
}

void print(std::vector<std::pair<int, int>>& arr) {
    for (auto & i : arr) {
        fout << i.first << " " << i.second << "\n";
    }
}

int main() {
    int N, G;
    std::vector<std::pair<int, int>> arr;

    readInput(arr, N, G);

    solve(arr, N, G);

    fin.close();
    fout.close();

    return 0;
}