# Dynamic programming question

• Danielm
In summary, the problem is to maximize the average grade of n projects with a given time constraint, using a set of functions for each course that determine the grade based on the time spent on the project. The knapsack algorithm may be applicable, but modifications will need to be made due to the different cost/reward structure. The running time of the algorithm should be polynomial in n, g, and H.
Danielm

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

Danielm said:

## 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:
Danielm said:

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

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

nrobidoux said:
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)

nrobidoux said:
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:
nrobidoux said:
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.

## 1. What is dynamic programming?

Dynamic programming is a problem-solving technique used in computer science and mathematics to solve complex optimization problems. It involves breaking down a larger problem into smaller subproblems and storing their solutions to avoid repeating calculations.

## 2. How is dynamic programming different from other problem-solving techniques?

Unlike other problem-solving techniques that solve each subproblem independently, dynamic programming uses the solutions of smaller subproblems to solve larger ones. This makes it more efficient and reduces the time and memory needed to solve the problem.

## 3. What are some common applications of dynamic programming?

Dynamic programming is commonly used in areas such as computer science, economics, and engineering. It is used to optimize solutions in areas like resource allocation, scheduling, and route planning. It is also used in algorithms for string processing and data compression.

## 4. What are the basic steps of solving a dynamic programming problem?

The basic steps of solving a dynamic programming problem include: identifying the optimal substructure, breaking down the problem into smaller subproblems, storing the solutions to the subproblems, and using those solutions to solve the larger problem.

## 5. What are the advantages of using dynamic programming?

Dynamic programming offers several advantages, including improved efficiency, reduced time and memory usage, and the ability to solve complex problems. It also allows for the reuse of solutions to subproblems, making it a more practical and efficient approach to problem-solving.

• Engineering and Comp Sci Homework Help
Replies
2
Views
878
• Programming and Computer Science
Replies
2
Views
965
• Precalculus Mathematics Homework Help
Replies
3
Views
963
• Topology and Analysis
Replies
7
Views
2K
• Programming and Computer Science
Replies
3
Views
2K
• Programming and Computer Science
Replies
2
Views
883
• Engineering and Comp Sci Homework Help
Replies
7
Views
2K
• Engineering and Comp Sci Homework Help
Replies
7
Views
2K
• Atomic and Condensed Matter
Replies
3
Views
834
• Precalculus Mathematics Homework Help
Replies
9
Views
2K