Answer to Question #197233 in Algorithms for emre

Question

Q1. Solve the following question to find best courses/payment using dynamic programming:

A graduate student may take any number of courses as a Teaching Assistant. There are five

courses and each associated with a payment. Each course has a number of hours needed and

the student is allowed to spend a maximum of 6 hours on TA duties. Find the best choice for

the grad student to maximize his/her income based on the following five courses specified as

(hours needed, payment received). -- (1,2, (4,5), (5,6) ), (2,3), (3,4)

Answer 1

The best possible variants:

$(1,2),(4,5)$

$(1,2),(5,6)$

$(1,2),(2,3),(3,4)$

$(4,5),(2,3)$

Maximal income will be at variant $(1,2),(2,3),(3,4)$, where:

hours needed: 6, payment received: 9.