# Dynamic programming question

## 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 Helper
Dearly Missed

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

Last edited:
QuantumQuest
Gold Member

## 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?

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
Gold Member
I'm totally stumped by this question.

What do you mean by that?

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
Homework Helper
Dearly Missed
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.)

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:
QuantumQuest