CS29003 - ALGORITHMS LABORATORY - ASSIGNMENT 5 - Dynamic Programming - Solved

Problem Statement
Recently you have joined a chemistry lab and they are leading a research on a system which consists of a sequence of independent and essential chemical reactions. Surprisingly the researchers of the lab have discovered a unique catalyst and it can be included in any of the reactions of the system. The use of the catalyst enhances the rate of the reaction and hence its probability of success also. Also they have proven that the probability of success of the reactions depends on the usage of the catalyst, typically expressed in terms of number of units involved in the reaction. The more the quantity (units) of catalyst is used in a reaction, the probability of success increases or remains the same, but never decreases. The probability of success of the entire system is the product of the probability of success of each of the individual reactions. Given the limited quantity (units) of the catalyst, the researchers want to gain the maximum success of the system. As an expert in algorithms, you are given the task of maximizing the success probability of the system with the constrained amount of the catalyst. You have to formulate a Dynamic Programming solution for the problem (use of memoization is NOT allowed).

You are given N reactions, numbered from 1 to N, all of which must be completed for the successful completion of reactions of the system. The system has a total of C units of catalyst (C ≥ N) that can be used in different reactions. Let e(k,p) denote the probability of success of the reaction k if p units of catalyst are used in the reaction. It is given that e(k,0) = 0 for all k, so at least one unit of catalyst must be used by each of the reaction. Also, for a reaction k, e(k,p) values are non-decreasing with increasing values of p (i.e., the chance of success never decreases if more units of catalyst are assigned to the reactions). You need to assign the C units of the catalyst to the N reactions so that the probability of success of the system is maximized.

You are required to design an efficient dynamic programming algorithm for the problem.

Part I
Write as comments at the very beginning in your program, the following clearly

1.    The definition of the subproblem that you choose.

2.    The recursive formulation used in the DP solution, including the base case. Write using notations as you have seen in text, do not write long sentences.

Partial marks will be awarded if you can figure out the recurrence.

1

Part II
Write a main() function to implement the dynamic programming. Read the input file as follows

1.    The first line contains the number of reactions N (assume N < 10)

2.    Read in C (assume C < 30. You can also assume C will be entered as ≥ N, no need to check).

3.    Read in the e(k,p) values for each reaction exactly in this order in a 2-d array (enter the values in each row in non-decreasing order): e(1,1),e(1,2),....,e(1,C) e(2,1),e(2,2),....,e(2,C)

....

e(N,1),e(N,2),....,e(N,C)

Sample input file
File: input.txt  

3

5

0.1 0.3 0.5 0.6 0.6

0.1 0.2 0.4 0.6 0.8

0.2 0.4 0.4 0.7 0.9

 

You have to print the followings exactly same as shown in the sample output file

1.    The maximum probability of success, of the system.

2.    The assignment of the catalyst in units to each of the reaction that gives the maximum success probability of the system.

Sample output file
File: output.txt  

0.012

reaction 1 : 2 reaction 2 : 2

reaction 3 : 1