How Can Dynamic Programming Optimize Study Hours for Maximum Grades?

[Danielm]

Homework Statement

Suppose it’s nearing the end of the semester and you’re taking n courses, each with a final project that still has to be done. Each project will be graded on the following scale: It will be assigned an integer number on a scale of 1 to g > 1, higher numbers being better grades. Your goal, of course, is to maximize your average grade on the n projects. You have a total of H > n hours in which to work on the n projects cumulatively, and you want to decide how to divide up this time. For simplicity, assume H is a positive integer, and you’ll spend an integer number of hours on each project. To figure out how best to divide up yourtime, you’vecome up with a set of functions{fi :i=1,2,...,n}(rough estimates, of course) for each of your n courses; if you spend h≤H hours on the project for course i, you’ll get a grade of f_i(h). (You may assume that the functions f_i are nondecreasing: if h' < h, then f_i(h')≤f_i(h).) So the problem is: Given these functions{f_i}, decide how many hours to spend on each project (in integer values only) so that your average grade, as computed according to the fi, is as large as possible. In order to be efficient, the running time of your algorithm should be polynomial in n, g, and H; none of these quantities should appear as an exponent in your running time.

Homework Equations

The Attempt at a Solution

I am pretty sure that I have to use the knapsack problem. In this case, it is a little bit different because in the knapsack problem each element is unique and have a different weight and different value. In this case the weight is the time that you spend in each class and the value your grade. I don't know how to apply the knapsack in this case hence we have to choose the f_i(h) for each h and i.

 

[Ray Vickson]

Homework Statement

Suppose it’s nearing the end of the semester and you’re taking n courses, each with a final project that still has to be done. Each project will be graded on the following scale: It will be assigned an integer number on a scale of 1 to g > 1, higher numbers being better grades. Your goal, of course, is to maximize your average grade on the n projects. You have a total of H > n hours in which to work on the n projects cumulatively, and you want to decide how to divide up this time. For simplicity, assume H is a positive integer, and you’ll spend an integer number of hours on each project. To figure out how best to divide up yourtime, you’vecome up with a set of functions{fi :i=1,2,...,n}(rough estimates, of course) for each of your n courses; if you spend h≤H hours on the project for course i, you’ll get a grade of f_i(h). (You may assume that the functions f_i are nondecreasing: if h' < h, then f_i(h')≤f_i(h).) So the problem is: Given these functions{f_i}, decide how many hours to spend on each project (in integer values only) so that your average grade, as computed according to the fi, is as large as possible. In order to be efficient, the running time of your algorithm should be polynomial in n, g, and H; none of these quantities should appear as an exponent in your running time.

Homework Equations

The Attempt at a Solution

I am pretty sure that I have to use the knapsack problem. In this case, it is a little bit different because in the knapsack problem each element is unique and have a different weight and different value. In this case the weight is the time that you spend in each class and the value your grade. I don't know how to apply the knapsack in this case hence we have to choose the f_i(h) for each h and i.

The knapsack solution applies only in the case that each $f_i$ has the form $f_i(h) = c_i h$ for some constant $c_i > 0$. If the $f_i$ do not have that form you need to find another way.

Note added in edit: the algorithm is similar to that of the knapsack problem, but some of the details are different, due to the different cost/reward structure. If you understand how/why the knapsack algorithm works, you ought to be able to figure out how to modify it for the current case.

 

[QuantumQuest]

Homework Statement

Suppose it’s nearing the end of the semester and you’re taking n courses, each with a final project that still has to be done. Each project will be graded on the following scale: It will be assigned an integer number on a scale of 1 to g > 1, higher numbers being better grades. Your goal, of course, is to maximize your average grade on the n projects. You have a total of H > n hours in which to work on the n projects cumulatively, and you want to decide how to divide up this time. For simplicity, assume H is a positive integer, and you’ll spend an integer number of hours on each project. To figure out how best to divide up yourtime, you’vecome up with a set of functions{fi :i=1,2,...,n}(rough estimates, of course) for each of your n courses; if you spend h≤H hours on the project for course i, you’ll get a grade of f_i(h). (You may assume that the functions f_i are nondecreasing: if h' < h, then f_i(h')≤f_i(h).) So the problem is: Given these functions{f_i}, decide how many hours to spend on each project (in integer values only) so that your average grade, as computed according to the fi, is as large as possible. In order to be efficient, the running time of your algorithm should be polynomial in n, g, and H; none of these quantities should appear as an exponent in your running time.

Homework Equations

The Attempt at a Solution

I am pretty sure that I have to use the knapsack problem. In this case, it is a little bit different because in the knapsack problem each element is unique and have a different weight and different value. In this case the weight is the time that you spend in each class and the value your grade. I don't know how to apply the knapsack in this case hence we have to choose the f_i(h) for each h and i.

I recommend to focus on the optimal substructure aspect of dynamic programming. As a hint, what if you assume that you have only h hours for projects i,...,n? Can you find the max expected grade? Can you write a recurrence relation that describes this?

 

[nrobidoux]

I recommend to focus on the optimal substructure aspect of dynamic programming. As a hint, what if you assume that you have only h hours for projects i,...,n? Can you find the max expected grade? Can you write a recurrence relation that describes this?

I'm totally stumped by this question.

 

[QuantumQuest]

I'm totally stumped by this question.

What do you mean by that?

 

[nrobidoux]

It wasn't meant in regards to your response. I had this problem as part of an assignment due midnight yesterday. In what seems to be my fashion, my brain somehow kicked in in just enough time so I could determine, articulate, and type my solution. Literally when I wrote that statement in this thread I thought I had an idea that would work out (and sat on it for a few days) only to determine it would not when I sat down and really looked at it.

Taking my algorithms class online. To me it's all alphabet soup and isn't natural to me. Luckily I'm at a spot where I have a lot of available time... seems I throw enough at these problems to find a solution. So far anyway... and so far been right all the time. (crosses-fingers)

 

[Ray Vickson]

It wasn't meant in regards to your response. I had this problem as part of an assignment due midnight yesterday. In what seems to be my fashion, my brain somehow kicked in in just enough time so I could determine, articulate, and type my solution. Literally when I wrote that statement in this thread I thought I had an idea that would work out (and sat on it for a few days) only to determine it would not when I sat down and really looked at it.

Taking my algorithms class online. To me it's all alphabet soup and isn't natural to me. Luckily I'm at a spot where I have a lot of available time... seems I throw enough at these problems to find a solution. So far anyway... and so far been right all the time. (crosses-fingers)

Do you have access to a textbook? This is a 100% standard problem, which can be found all over the place.

If you have no book, try searching on-line. I recommend that you avoid the computer-science-oriented articles on dynamic programming and go instead to the "operations research" versions, by using key words 'dynamic programming + operations research'. (These are closer to the original Bellman form of the subject, rather than going into hash tables and other more computer-oriented aspects.)

 

[nrobidoux]

I do have the textbook. The lecture and the book are greek to me. So I'll go over them a few times, watch other Youtube videos about the topic, etc. When I look at the homework, with few exceptions, I'm like, "Huh?!?" And then I start pounding the square peg in the round hole. Given enough time and hammering... it fits. (So far 100% on homework. :D)

I do search online. I came across many homework assignments, free PDF copies of the book, and one solution. Since I could not understand it I kept going. Came up with:

1.) Precompute the grades for each class from 1..n hours.
2.) Sort each column (hours) decreasing order in a new quantity (grade/hrs; class id) by grade/hrs
3.) Find all factors of n from n...n/2 (i.e. n=10 {10x1}, {9x1, 1x1}, {8x1, 2x1}, {8x1,1x2}...
(Can be done recursively, probably better approach but was running out of time)
4.) Iterating through each set, look at top j elements queue skipping any where the class has alrdy been accounted for at an earlier step (j=1 where 9x1, j=2 where 1x2, etc)
5.) Sum those elements, if higher they are the new optimal solution

The solution I saw online was nothing like that. Looked as though they simply did step #1 and iterated through the table in a certain fashion.

I believe my solution has elements of the backpack problem but not using every aspect of it.

Onto this week's homework adventure. :)

 

[QuantumQuest]

I believe my solution has elements of the backpack problem but not using every aspect of it.

Although I agree to the point that Ray Vickson made above - to learn about dynamic programming in a more pure fashion, if you are learning about algorithms in an online class, take a look at Stanford online class Algorithms 1 and 2, taught by Tim Roughgarden, given on Coursera. I took both as a refresher some years ago and they're great. Instructor discusses and explains how each programming style in general and each algorithm works in a mathematical fashion and leaves the implementations as homework assignments. I especially found the coverage about dynamic programming very satisfactory, provided (this holds for the entirety of both courses) that you do the respective relevant readings - your "homework" in short and even more.