You are not logged in. Please login at www.codechef.com to post your questions!

×

Sorting sets as per a return value

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.

asked 19 Mar '13, 14:00

karanahluwalia's gravatar image

2★karanahluwalia
1111
accept rate: 0%


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 :D

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

link

answered 19 Mar '13, 15:44

kuruma's gravatar image

3★kuruma
17.7k72143209
accept rate: 8%

edited 19 Mar '13, 15:52

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×801
×163

question asked: 19 Mar '13, 14:00

question was seen: 5,902 times

last updated: 19 Mar '13, 15:52