# Dynamic programming recursion

In a book by Wayne Winston for operations research I found this question.

Here's how I did it:
Let $t$ be the no.of subjects to pass and let h be the no.of hours she has in hand for studying.
Then $f_t(h)$ be the probability of passing subjects t,t+1,..3 when h hours are in hand. Let $x_t$ be the no.of hours spent on subject t.
$0<=x_t<=h; h\in {0,1,2,3,4}$

Then $f_3(4)=0.5 \\ f_3(3)=0.44 \\f_3(2)=0.4\\f_3(1)=0.3\\f_3(0)=0.1$
Let $P_t(x_t)$ be the probability of passing subject t when $x_t$ hours are spent on it.

$f_t(h)=max${${P_t(x_t)}+f_{t+1}(h-x_t)$}
According to this I get
$f_(4)=$max$P_1(0)+f_2(4)=0.98\\P_1(1)+f_2(3)=1\\P_1(2)+f_2(2)=1\\P_1(3)+f_2(1)=0.93\\P_1(0)+f_2(4)=0.425$

The answer I get is she should study French for 1 hour, German for 1 hour and Stat for two hours. But the answer given in the book says French 1 hour, German 0 hours, Stat 3 hours.

What's wrong with my method? And what is the probability of passing at least one subject ?

• have you worked with routing algorithms? Dijkstra algorithm? As this solves the problem of finding the route by imagining the matrix as a nodes then iterating through would be my first guess – Chinny84 Jul 22 '15 at 14:50

I have a different approach.

indices:

$ij$: The amount of hours i Angie is learning for course j.

$i \in \{0,1,2,3,4\}$

$j \in \{1,2,3\}$

variables:

$$x_{ij}=\begin{cases} 1, \ \texttt{if Angie learns i hours for course j} \\ 0, \ \texttt{else}\end{cases}$$

$$f_{ij}=\texttt{probability, that Angie passes course j, if she is learning i hours}$$

constraint 1: Angie is learning 4 hours a week

$$\sum_{i=0}^4 \sum_{j=1}^3 i \cdot x_{ij}=4$$

constraint 2: Only one hours/course combination for each course

$$\sum_{i=0}^4 x_{ij}=1 \ \ \ \ \forall j \in \{1,2,3\}$$

objective function:

Because of the comments of joriki the objective function is

$$\texttt{max} \ \ \ 1-\prod_{j=1}^3 \left(1- \sum_{i=0}^4 f_{ij} \cdot x_{ij} \right)$$

• Your objective function is the sum of the probabilities of passing the individual tests. The intended objective function is the probability of passing at least one test, i.e. the complement of the product of the complements of the probabilities. – joriki Jul 22 '15 at 15:28
• On one hand I understand your argument (more or less). On the other hand I do not really know how to change the objective function. Could you show me (us), how you would write the objective function ? – callculus Jul 22 '15 at 15:42
• $$1-\prod_{j=1}^3\left(1-\sum_{i=0}^4f_{ij}x_{ij}\right)$$ – joriki Jul 22 '15 at 15:44
• This looks fine. I will edit my answer. Many thanks for this helpful hint. – callculus Jul 22 '15 at 15:51
• @sam_rox: Yes, exactly. The way things are set up in this answer, $\sum_{i=0}^4f_{ij}x_{ij}$ is the probability of passing test $j$. (I wouldn't have set it up like that, but it's correct.) Then one minus that is the probability of not passing, i.e. of failing test $j$. The product of those probabilities for all three tests is the probability of failing all of them. And one minus that is the probability of not failing all of them, i.e. of passing at least one. – joriki Jul 22 '15 at 17:34