A college student has 7 days remaining before final examinations begin in her fo

Question

A college student has 7 days remaining before final examinations begin in her four courses, and she wants to allocate this study time as a effectively as possible. She needs at least 1 day on each course, and she likes to concentrate on just one course each day, so she wants to allocate 1, 2, 3, 4 days to each course. Having recently taken an OR course, she decides to use dynamic programming to make these allocations to maximize the total grade points to be obtained from the four courses. She estimates that the alternative allocations for each course would yield the number of grade points shown in the following table: Estimated Grade Points Course Study Days 1 2 3 4 1 5 4 4 3 6 6 4 6 8 7 5 8 8 9 8 Solve this problem by dynamic programming.

Explanation / Answer

There are four stages. At stage i, let xi denote the number of days left for study. Let yi denote the number of days allocated for course i. Let ri(yi) be the return (= grade points got) when yi days are allocated to course i. Let Fi(xi) be the optimum return for stages i, i+1, …, 4. Thus Fi(xi) where and F5(x5) = 0= F5(x4-y4) F1(7) gives us the optimal solution to the given problem. Stage 4. Since the student should devote at least one day for each course, x4=1,2,3,4 = y4 Hence F4(x4) = r4(y4) x4 1 2 3 4 F4(x4) 6 7 9 9 * y4 1 2 3 4 Stage 3: x3 = 2,3,4,5 F3(x3) = max {r3(y3) + F4(x3 - y3)} y3 ? x3 r3(y3) + F4(x3 - y3) y3 x3 2 3 4 5 1 2+6= 8 2+7= 9 4+6=10 2+9=11 4+7=11 2+9=11 4+9=13 2 - F3(x3) y3* 8 1 10 2 7+6=13 13 3 7+7=14 8+6=14 14 3 or 4 3 - - 4 - - - Stage 1: Though we should only find F1(7), we find F1(x1) for x1 = 4, 5, 6, 7. F1(x1) = max {r1(y1) + F2(x1 – y1)} y 1 x1 4 5 6 7 Optimum Solution: y1 = 2, y2 = 1, y3 = 3, y4 = Optimum Total Grade Points = F1 (7) = 23 1 1 3+13=16 3+16=19 3+18=21 3+19=22 r1(y1) + F2(x1- y1) 2 3 4 F1(x1) - - - 16 - - 5+13=18 19 - 5+15=20 6+13=19 21 5+18=23 6+15=21 7+13=20 23 Brute Force Verification D1 D2 D3 D4 Tot Gr pts 1 1 1 4 3+5+2+9=19 1 1 2 3 3+5+4+9=21 1 1 3 2 3+5+7+7=22 1 1 4 1 3+5+8+6=22 1 2 1 3 3+5+2+9=19 1 2 2 2 3+5+4+7=19 D1 D2 D3 D4 Tot Gr pts 2 2 1 2 5+5+2+7=19 2 2 2 1 5+5+4+6=20 2 3 1 1 5+6+2+6=19 3 1 1 2 6+5+2+7=20 3 1 2 1 6+5+4+6=21 3 2 1 1 6+5+2+6=19 4 1 1 1 7+5+2+6=20

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.