Pagini recente » Cod sursa (job #189306) | Cod sursa (job #1473493) | Cod sursa (job #2975628) | Cod sursa (job #1982153) | Cod sursa (job #3288141)
// 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;
}