Year_2/Algorithms/greedy-knapsack.cc


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

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<int> 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;
}