Dynamic programming question

1. May 16, 2016

Danielm

1. The problem statement, all variables and given/known data

2. Relevant equations

3. 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.

2. May 16, 2016

Ray Vickson

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.

Last edited: May 16, 2016
3. May 16, 2016

QuantumQuest

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?

4. Nov 2, 2016

nrobidoux

I'm totally stumped by this question.

5. Nov 3, 2016

QuantumQuest

What do you mean by that?

6. Nov 3, 2016

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)

7. Nov 3, 2016

Ray Vickson

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.)

8. Nov 6, 2016

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. :)

Last edited: Nov 6, 2016
9. Nov 6, 2016

QuantumQuest

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.