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

using namespace std;

template <class InputIt, typename T, typename F1, typename F2>
InputIt greedy_knapsack(InputIt first, InputIt last, const T& b, F1 price, F2 weight)
{
	using Item = typename InputIt::value_type;
    T init(0);
    std::sort(first, last, [&](Item& i1, Item& i2) {
    	if (price(i1) == price(i2)) return weight(i1) < weight(i2);
    	if (weight(i1) == weight(i2)) return price(i2) < price(i1);
    	return weight(i1) * price(i2) < weight(i2) * price(i1); 
    });
    InputIt it = std::find_if(first, last, [&](Item& i) { 
    	return (init += weight(i)) > b;
    });
    return it;
}

struct my_item
{
    int _a; // weight
	int _p; // 
};


int main(int argc, char const *argv[])
{
	std::vector<my_item> v{{4,2}, {10,3}, {20, 4}, {7,2}};
	auto it1 = begin(v);
    auto it2 = greedy_knapsack(begin(v), end(v), 15, 
    	[](my_item& i)->int { return i._p; },
    	[](my_item& i)->int { return i._a; }
    );
    for (; it1 != it2; ++it1) {
    	cout << '(' << it1->_a << ", " << it1->_p << ')';
    }
	return 0;
}