Question

Can you answer #3?

2. (12 marks) Use dynamic programming for the following 'Make Change problem': Number of denominations, N: 4 Denomination values, dl : 7, 2, 3,6 Amount for which change is to be made, A: 17. how the values of arrays Cl and SI (shown in class) for each denomination or iteration. 3. (8 marks) Implement Make Change problem' using dynamic programming and homw the outut fort he gdgg show the output for the input from Question 2.

Answer 1

package dp;

public class CoinChangingProblem {
  

   public static void coinChange(int ar[],int d){
       int dp[]=new int[d+1]; //make array of d+1
       for(int i=0;i<dp.length;i++){ //Initialize it with 0
           dp[i]=0;
       }
       dp[0]=1; //first element 0
       for(int i=0;i<ar.length;i++){ //for each coin
           for(int j=ar[i];j<=d;j++){ //for ar[i] to d
               dp[j]=dp[j]+dp[j-ar[i]]; //add present element + previously calculated no
           }
       }
       System.out.println(dp[d]); //last value will be ans
   }
   public static void main(String[] args) {
       int c[]={7, 2, 3, 6};
       int A=17;
       coinChange(c,A);

   }

}

output

10