Sorting sets as per a return value

general
,
1

i have the following problem
We have a set S of n potential investments, each given by a pair of floating point numbers (amount, estimated return) There is a total amount A to invest; we want to select investments to maximise the return on this amount.

please explain how do i order the investments using the ratio estimated return/amount, in nlogn. is this using quick sort? i can calculate the ratios in O(n) then how do i keep an index as to which ratio belongs to which investment?

am trying to solve it using the following algo

1.order the investments according to the decreasing ratio r/a
2.allocate available money to the investments in such order. I.e. buy all the first investment, then use available money to buy the second investment, then the third, etc, until the money is finished.

2

Hello,

I guess this is a DP problem, but your sorting idea is also not too bad…

What you have is a compound data type, called investment, that has two “members” associated with it:

an amount and an estimated return.

And you want, as you clearly pointed out, sort them by a given ratio…

What you can do, is to use a comparison function devised specifically to compare investiments:

You compare two investments by their ratios and sort them accordingly:

In C++ you can do something like:

struct investment
{
	double amount, expected_return;
};

bool cmp(investment a, investment b)
{
	return ((a.expected_return)/a.amount)<((b.expected_return)/b.amount);
}

And then you can use your newly defined cmp function as a third argument for the built-in std::sort function and you’ll have an array with the ordered investments :smiley:

Below you can find a complete example:

#include <iostream>
#include <algorithm>
using namespace std;

struct investment
{
    double amount, expected_return;
};

bool cmp(investment a, investment b)
{
    return ((a.expected_return)/a.amount)<((b.expected_return)/b.amount);
}

int main()
{
	investment array[5] = {{10.0, 1.0},{1.0, 100.0},{12.0, 8.0},{13.0, 9.0},{15.0, 1.0}};
	sort(array,array+5,cmp);
	for(int i = 0; i < 5; i++)
	{
		cout << array[i].amount << " " << array[i].expected_return << endl;
	}
	return 0;
}

Best regards,

Bruno