From 9cb77bf8a8d9e8bcb04a9d7fadd85329539113b8 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Sat, 21 Jan 2023 19:22:56 +0100 Subject: add knapsack --- Year_2/Algorithms/greedy-knapsack.cc | 40 ++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) create mode 100644 Year_2/Algorithms/greedy-knapsack.cc diff --git a/Year_2/Algorithms/greedy-knapsack.cc b/Year_2/Algorithms/greedy-knapsack.cc new file mode 100644 index 0000000..c385499 --- /dev/null +++ b/Year_2/Algorithms/greedy-knapsack.cc @@ -0,0 +1,40 @@ +#include +#include +#include +#include + +using namespace std; + +int +main(int argc, char** argv) +{ + int ts = (argc > 1) ? stoi(argv[1]) : 100; + ifstream fin("input.txt"); + ofstream fout("output.txt"); + + for (int i = 0; i < ts; ++i) { + int n, target; + vector v; + fin >> n >> target; + v.resize(n); + + for (int j = 0; j < n; ++j) { + fin >> v[j]; + } + + sort(v.begin(), v.end(), [](int a, int b) { + return a > b; + }); + + int result { 0 }; + for (int j = 0; j < min(target, n); ++j) + result += v[j]; + + fout << result << endl; + } + + fin.close(); + fout.close(); + + return 0; +} -- cgit v1.2.3-18-g5258