I need help with number 2 For each of the following problems give: A. The functi

Question

I need help with number 2

For each of the following problems give: A. The function that represents the quantity to be optimized. This includes specifying the parameters. E.g. F(I, J): this represents the maximum number of coins that the robot can pick up from a rectangle of size IxJ made up of the first I rows and first J columns.. B. The recurrence formula: the formula that specifies the recurrence relation that represents the relationship between larger problems and smaller problems. E.g. for the robot problem F(l, J):- max {F(l, J), F(I, J)} + 6 i j where 5 i, j - 1 if there is a coin in the i j square and 0 if not C. The base cases: E.g. F(0, J)- F(I, 0) _ 0 for all I from 0 to N and all J from 0 to M D. The final solution: E.g. F(N, M) if the original problem is stated as an N times M board E. The pseudo code for the iterative algorithm to fill in a table that would be used for a bottom up dynamic programming solution 1. Given an unlimited supply of coins of denominations 1 -d_1

Explanation / Answer

Following is the pseudo code of required algorithm:

Note that 0-indexing is used, coins are given index 0, 1, ... total_coins-1 and dj represents value of jth coin

change_possible( coins di, value v )
   dp_table[ v + 1 ][total_coins];

   //we write answer for base case when value = 0,
   //we put it 1 to mark that it is possible
   for i = 0 to total_coins:    //it actually means for( i = 0; i < total_coins; i++ )
       dp_table[ 0 ][ i ] = 1;

   //dynamic programming
   for i = 1 to v+1: //it actually means for( i = 0; i < v+1; i++ )
       for j = 0 to total_coins:
           possible_is = False;
           //say we choose coin dj
           if( dj <= i ){
               if dp_table[ i - dj ][ j ] == True:
                   possible_is = True;
           }
           //now we don't choose dj
           if j >= 1{
               if dp_table[ i ][ j-1 ] == True:
                   possible_is = True;
           }
           dp_table[i][j] = possible_is;

   return dp_table[ v ][ total_coins- 1 ];
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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