Algorithm Question Maximize Average of Functions

Question

Hello,

I have a set of N non-decreasing functions each denoted by F_i(h), where h is an integer. The functions have numeric values.

I'm trying to figure out a way to maximize the average of all of the functions given some total H value.

For example, say each function represents a grade on an assignment. If I spend h hours on assignment i, I will get g = F_i(h) as my grade. I'm given H hours to finish all of the assignments. I want to maximize my average grade for all assignments.

Can anyone point me in the right direction to figure this out? I just need a generic algorithm in pseudo code and then I can probably adapt quickly from that.

EDIT: I think dynamic programming could be used to figure this out but I'm not really 100% sure.

EDIT 2: I found an example in my algorithms book from when I was in university that is almost the exact same problem take a look here on Google Books.

Answer 1

I don't know about programming, but in mathematics functions of functions are called functionals, and the pertinent math is calculus of variations.

Answer 2

Genetic Algorithms are sometimes used for this sort of a thing, but the result you'll get won't be optimal, but near it.
For a "real" solution (I always feel genetics is sort of cheating) if we can determine some properties of the functions (Is function X rising? Do any of them have asymptotes we can abuse? etc.), then you need to design some analyzing mechanism for each function, and take it from there. If we have no properties for any of them, they could be anything. My math isn't excellent, but those functions could be insane factorials^99 that is zero unless your h is 42 or something.
Without further info, or knowledge that your program could analyze and get some info. I'd go genetics. (It would make sense to apply some analyzing function on it, and if you find some properties you can use, use them, otherwise turn to the genetic algorithm)

Answer 3

If the functions in F are monotonically increasing in their domains then parametric search is applicable (search for Meggido).

Answer 4

Have a look at The bounded knapsack problem and the dynamic programming algorithm given.

Answer 5

I have one question: how many functions and how many hours do you have ?

It seems to me that an exhaustive search would be quite suitable if none is too high.

The Dynamic Programming application is quite easy, first consider:

F1 = [0, 1, 1, 5] # ie F1[0] == 0, F1[1] == 1
F2 = [0, 2, 2, 2]

Then if I have 2 hours, my best method is to do:

F1[1] + F2[1] == 3

If I have 3 hours though, I am better off doing:

F1[3] + F2[0] == 5

So the profile is anarchic given the number of hours, which means that if a solution exists it consists in manipulating the number of functions.

We can thus introduce the methods one at a time:

R1 = [0, 1, 1, 5] # ie maximum achievable (for each amount) if I only have F1
R2 = [0, 2, 3, 5] # ie maximum achievable (for each amount) if I have F1 and F2

Introducing a new function takes O(N) time, where N is the total number of hours (of course I would have to store the exact repartition...)

Thus, if you have M functions, the algorithm is O(M*N) in terms of number of functions execution.

Some functions may not be trivial, but this algorithm performs caching implicitly: ie we only evaluate a given function at a given point once!

I suppose we could be better if we were able to use the increasing property into consideration, but I daresay I am unsure about the specifics. Waiting for a cleverer fellow!

Since it's homework, I'll refrain from posting the code. I would just note that you can "store" the repartition if your R tables are composed of pairs (score,nb) where nb indicates the amount of hours used by the latest method introduced.

Answer 6

Have a look at linear programming, the section on integer programming