#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <ctime>

std::vector<double> Sort(std::vector<double> weights, const double pounds) {
	std::sort(weights.begin(), weights.end());
	std::vector<double>::iterator iter = weights.end();
	double total=0;
	while(total < pounds) {
		--iter;
		total += *iter;
	}
	return std::vector<double>(iter, weights.end());
}

std::vector<double> JimMischel(std::vector<double> weights, const double pounds) {
	std::make_heap(weights.begin(), weights.end());
	std::vector<double> result;
	double total=0;
	while(total < pounds) {
		std::pop_heap(weights.begin(), weights.end());
		result.push_back(weights.back());
		total += weights.back();
		weights.pop_back();
	}
	return result;
}

std::vector<double> SoapBox(std::vector<double> weights, const double pounds) {
	std::greater<double> pred;
	std::vector<double> result(1, weights[0]);
	double total=weights[0];
	double lightest=weights[0];
	unsigned int i;
	for(i=0; i<weights.size() && total<pounds; ++i) {
		double curweight = weights[i];
		result.push_back(curweight);
		total += curweight;
		if (curweight < lightest)
			curweight = lightest;
	}
	std::make_heap(result.begin(), result.end(), pred);
	for( ; i<weights.size(); ++i) {
		double curweight = weights[i];
		if (curweight>lightest && total-lightest+curweight>=pounds) {
			do {
				std::pop_heap(result.begin(), result.end(), pred);
				total -= result.back();
				result.pop_back();
				lightest = result.front();
			} while(total-lightest+curweight >= pounds);
			result.push_back(curweight);
			std::push_heap(result.begin(), result.end(), pred);
			total += curweight;
			if (curweight < lightest)
				curweight = lightest;
		}
	}
	return result;
}

std::vector<double> NeilG(std::vector<double> weights, const double pounds) {
	std::vector<double> spared;
	std::vector<double> dead;
	std::vector<double> less;
	std::vector<double> greater;
	std::vector<double> result;
	double deadtotal = 0;
	while(weights.size() && weights.front()!=weights.back()) {
		double greaterweight=0;
		std::sort(weights.begin(), weights.begin() + (weights.size()>5?5:weights.size()));
		double guess = weights[weights.size()>2?2:1];
		for(unsigned int i=0; i<weights.size(); ++i) {
			if (weights[i]<guess)
				less.push_back(weights[i]);
			else  {
				greater.push_back(weights[i]);
				greaterweight += weights[i];
			}
		}
		if (deadtotal + greaterweight >= pounds) {
			weights = greater;
			greater.clear();
			less.clear();
		} else {
			deadtotal += greaterweight;
			if (greater.size())
				result.insert(result.end(), greater.begin(), greater.end());
			greater.clear();
			weights = less;
			less.clear();
		}
	}
	while(deadtotal<pounds && weights.size()) {
		result.push_back(weights.front());
		deadtotal += weights.front();
		weights.pop_back();
	}
	return result;
}

#define COUNT 10000000
int main() {
	//srand(time_t(NULL));  //omitted for consistancy
	std::vector<double> weights;
	weights.reserve(COUNT);
	std::vector<double> result0, result1, result2, result3;
	result1.reserve(100);
	result2.reserve(100);
	result3.reserve(100);
	clock_t begin, end;
	double total;
	for(unsigned int i=0; i<COUNT; ++i) {
		double big = rand()*RAND_MAX + rand();
		double inrange = big*100 /RAND_MAX/RAND_MAX + 100;
		weights.push_back(inrange);
	}

	result0 = Sort(weights, 3000);
	begin = clock();
	result0 = Sort(weights, 3000);
	end = clock();
	std::sort(result0.begin(), result0.end());
	std::cout << "Sort:       " << (end-begin) << " ticks: ";
	total =0;
	for(unsigned int i=0; i<result0.size(); ++i)
		total += result0[i];
	std::cout << result0.size() << " people, " << total << "lb (";
	for(unsigned int i=0; i<result0.size(); ++i)
		std::cout << (int(result0[i]*10000000)%10);
	std::cout << ")\n";


	result1 = JimMischel(weights, 3000);
	begin = clock();
	result1 = JimMischel(weights, 3000);
	end = clock();
	std::sort(result1.begin(), result1.end());
	std::cout << "JimMischel: " << (end-begin) << " ticks: ";
	total =0;
	for(unsigned int i=0; i<result1.size(); ++i)
		total += result1[i];
	std::cout << result1.size() << " people, " << total << "lb (";
	for(unsigned int i=0; i<result1.size(); ++i)
		std::cout << (int(result1[i]*10000000)%10);
	std::cout << ")\n";

	result2 = SoapBox(weights, 3000);
	begin = clock();
	result2 = SoapBox(weights, 3000);
	end = clock();
	std::sort(result2.begin(), result2.end());
	std::cout << "SoapBox:    " << (end-begin) << " ticks: ";
	total =0;
	for(unsigned int i=0; i<result2.size(); ++i)
		total += result2[i];
	std::cout << result2.size() << " people, " << total << "lb (";
	for(unsigned int i=0; i<result2.size(); ++i)
		std::cout << (int(result2[i]*10000000)%10);
	std::cout << ")\n";

	result3 = NeilG(weights, 3000);
	begin = clock();
	result3 = NeilG(weights, 3000);
	end = clock();
	std::sort(result3.begin(), result3.end());
	std::cout << "NeilG:      " << (end-begin) << " ticks: ";
	total =0;
	for(unsigned int i=0; i<result3.size(); ++i)
		total += result3[i];
	std::cout << result3.size() << " people, " << total << "lb (";
	for(unsigned int i=0; i<result3.size(); ++i)
		std::cout << (int(result3[i]*10000000)%10);
	std::cout << ")\n";

	return 0;
}

Timeout