Answer to Question #38564 in Quantitative Methods for Sheila Koomson

Question

Consider the following (unrealistic!) investment 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.One may select each investment (a,r) as a whole (spending all of a, and getting r return) or only can select only a fraction f (spending (f*a), and getting (f*r) return). The estimated return of a set of selections is the sum of the returns of the individual selections. Obviously, in selecting elements of S, we cannot spend more than the total amount A available.Describe an efficient algorithm for computing the maximum estimated return that can be realised with amount A and set of investments S. What is the time complexity of your algorithm (in big-oh notation)? Is it the best possible? It is fine to describe your algorithm in words and/or pseudocode; there's no need to include code in a programming language.