This is a variaton of the 0-1 knapsack problem

A student, Bob is taking his math exam which consists of n questions. He notices that the professor has assigned points { p1, p2, ..., pn } to each problem according to the professor's opinion of the difficulty of the problem. Bob wants to maximize the total number of points he earns on the exam, but he is worried about running out of time since there is only T minutes for the exam. He estimates that the amount of time it will take him to solve each of the n questions is { t1, t2, ..., tn }. You can assume that Bob gets full credit for every question he answers completely. create an algorithim to help Bob select which questions to answer to maximize his total points earned. Note: NO partial credit is assigned to problems that are only partially completed.

(a) Verbally describe a Dynamic Programing algorithm to solve this problem.

(b) Give pseudo code with enough detail to obtain the running time, include the formula used to fill the table or array.

(c) What is the running time of your algorithm? Explain.

(d) Would Bob use this algorithm if the professor gave partial credit for partially completed questions on the exam? Discuss.