fork(1) download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. template <class InputIt, typename T, typename F1, typename F2>
  8. InputIt greedy_knapsack(InputIt first, InputIt last, const T& b, F1 price, F2 weight)
  9. {
  10. 	using Item = typename InputIt::value_type;
  11.     T init(0);
  12.     std::sort(first, last, [&](Item& i1, Item& i2) {
  13.     	if (price(i1) == price(i2)) return weight(i1) < weight(i2);
  14.     	if (weight(i1) == weight(i2)) return price(i2) < price(i1);
  15.     	return weight(i1) * price(i2) < weight(i2) * price(i1); 
  16.     });
  17.     InputIt it = std::find_if(first, last, [&](Item& i) { 
  18.     	return (init += weight(i)) > b;
  19.     });
  20.     return it;
  21. }
  22.  
  23. struct my_item
  24. {
  25.     int _a; // weight
  26. 	int _p; // 
  27. };
  28.  
  29.  
  30. int main(int argc, char const *argv[])
  31. {
  32. 	std::vector<my_item> v{{4,2}, {10,3}, {20, 4}, {7,2}};
  33. 	auto it1 = begin(v);
  34.     auto it2 = greedy_knapsack(begin(v), end(v), 15, 
  35.     	[](my_item& i)->int { return i._p; },
  36.     	[](my_item& i)->int { return i._a; }
  37.     );
  38.     for (; it1 != it2; ++it1) {
  39.     	cout << '(' << it1->_a << ", " << it1->_p << ')';
  40.     }
  41. 	return 0;
  42. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin 
Standard input is empty
stdout 
(4, 2)(10, 3)
https://ideone.com/9ZK6ol
greedy knapsack
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!