views:

167

answers:

6

Hello,

I have a set of N non-decreasing functions each denoted by Fi(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 = Fi(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.

+3  A: 

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

duffymo
Calc. var. can not help here at all - this is a discrete problem.
AVB
The proper framework for this will be "nonlinear integer programming with linear constraints", one constraint, actually.
AVB
@AB - I think I made it clear in the first phrase of the sentence that I wasn't talking about the discrete problem.
duffymo
A: 

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)

Rubys
A: 

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

sisis
A: 

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

Mads Ravn
Why I think its bounded knapsack problem? Number of hours can only be one of {0,1,...,H}.
TheMachineCharmer
@TheMachineCharmer: Ups, sorry. "Thinko" on my part. Thanks for the heads-up.
Mads Ravn
Do either of you have the pseudo code for that algorithm? I understand the math but can't understand implementing it with pseudo code. Thanks!
@TheMachineCharmer: Looking at it again I actually think we have the 0-1 version, as we can only use the functions once. @paradoxperfect: The dyn. programming algorithm seems pretty straightforward, if you can adapt it to your problem. Since this is homework, I think you should try yourself. If you run into problems you can always update the question with more info and ask for help again.
Mads Ravn
A: 

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.

Matthieu M.
+1  A: 

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

Unreason