Design a dynamic programming algorithm to find the value of


1. Write a program to solve the Longest Common Subsequence problem using dynamic programming. For example, if the input is X = ABCBDAB and Y = BDCABA, then the output of your program should be BCBA.

2. Suppose you need to create a work plan, and each week you have to choose a job to undertake. The set of possible jobs is divided into low-stress and high-stress jobs.

If you select a low-stress job in week i, then you get a revenue of li dollars; if you select a high-stress job, you get a revenue of hi dollars. The catch, however, is that in order for you to take on a high-stress job in week i, it's required that you rest in weeki - 1 because you need a full week of prep time to get ready for the stress level (It's okay to choose a high-stress job in week 1.) On the other hand, you can take a low-stress job in weeki even if you have done a job (of either type) in week i-1.

So, given a sequence of n weeks, a plan is speci?ed by a choice of "low-stress", "high-stress" or "none" for each of the n weeks, with the constraint that if "high-stress" is chosen for week i> 1, then "none" must be chosen for week i - 1. The value of the plan is determined in the natural way; for each i, you add li to the value if you choose "low-stress" in week i, and you add hi to the value if you choose "high-stress" in week i. (You add 0 if you choose "none" in week i.)

Example: Suppose n=4, and the values of li and hiare given by the following table. Then the plan of the maximum value would be to choose "none" in week 1, a high stress job in week 2, and low-stress jobs in weeks 3 and 4. The value of this plan would be 0+50+10+10=70.

i

Week 1

Week 2

Week 3

Week 4

l

10

1

10

10

h

5

50

5

1

Design a dynamic programming algorithm to find the value of the optimal plan. Implement your algorithm using JAVA programming language.

Solution Preview :

Prepared by a verified Expert
Data Structure & Algorithms: Design a dynamic programming algorithm to find the value of
Reference No:- TGS02245278

Now Priced at $40 (50% Discount)

Recommended (96%)

Rated (4.8/5)