#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> Heap(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;
}

struct PartitionPred {
	const double pounds;
	PartitionPred(const double lb) : pounds(lb) {}
	bool operator()(double lb) {return lb<pounds;}
};

std::vector<double> NeilG(std::vector<double> weights, const double pounds) {
	std::vector<double>::iterator spared = weights.begin();
	std::vector<double>::iterator dead = weights.end();
	std::vector<double>::iterator mid;
	std::vector<double>::iterator i;
	double deadtotal = 0;
	while(dead > spared && *spared!=*(dead-1)) {
		ptrdiff_t count = std::distance(spared, dead);
		if (count > 5) count = 5;
		std::sort(spared, spared + count);
		double guess = spared[count/2];
		mid = std::partition(spared, dead, PartitionPred(guess));
		if (mid == spared) { 
			for(i = spared+1; i<dead; ++i) {
				if (*i > guess) {
					mid = std::partition(spared, dead, PartitionPred(guess=*i));
					break;
				}
			}
		} else if (mid == dead) { 
			for(i = spared; i<dead; ++i) {
				if (*i > guess) {
					mid = std::partition(spared, dead, PartitionPred(guess=*i));
					break;
				}
			}
		}
		double greaterweight=0;
		for(i=mid; i<dead; ++i)
			greaterweight += *i;
		if (deadtotal + greaterweight >= pounds) {
			spared = mid;
		} else {
			deadtotal += greaterweight;
			dead = mid;
		}
	}
	while(deadtotal<pounds && dead>spared) {
		--dead;
		deadtotal += *dead;
	}
	return std::vector<double>(dead, weights.end());
}

#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, result4;
	result1.reserve(20);
	result2.reserve(20);
	result3.reserve(20);
	result3.reserve(20);
	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 = Heap(weights, 3000);
	begin = clock();
	result1 = Heap(weights, 3000);
	end = clock();
	std::sort(result1.begin(), result1.end());
	std::cout << "Heap:       " << (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