Question

Write a C code for

Modified Change problem:

Apply the dynamic programming algorithm to find all the solutions to the change-making problem for the denominations 1, 3, 5 and the amount n = 9

Answer 1

Total 6 solutions are possible, and they are The coins which we have {1, 3, 5} With max number of coins of 5 the denomination, n= 9 coin of 5= 1, remaining 4, coin of 3= 3, remaining 1 coin of 1 is 1 {1,3,5} {1,1,1,1,5} similarly, for most number of 3 coins coins of 3=> 9/3= 3, remaining = 0 {3,3,3} similarly, rest can be computed {1,1,1,3,3} {1,1,1,1,1,1,3} {1,1,1,1,1,1,1,1,1}

Code in c

1 #include<stdio.h> #include<string> 2 3 4 int possiblewayschangeorder(int changemakingcoinorder[], int dcoinssize, int n); int main() 5 6 { 7 8 9 int denominationcoins[] = {1, 3, 5}; int dcoinssize = sizeof(denominationcoins) / sizeof(denominationcoins[0]); int n = 9; printf("%d", possiblewayschangeorder(denominationcoins, dcoinssize, n)); return 0; 10 11 12 } 13 14 15 int possiblewayschangeorder(int changemakingcoinorder[], int dcoinssize, int n) 16 { 17 18 int coin, making; int changemaking[n + 1][dcoinssize]; for (int i = 0; i < dcoinssize; i++) changemaking[0][i] = 1; 19 20 21 22 for (int i = 1; i<n + 1; i++) 23 24 { 25 for (int j = 0; j < dcoinssize; j++) 26 27 ܒܝܕ 28 29 coin = (i - changemakingcoinorder[j] >= 0) ? changemaking[i - changemakingcoinorder[j]][j] : 0; making = (j >= 1) ? changemaking[i][j - 1] : 0; changemaking[i][j] = coin + making; 30 31 } 32 } 33 return changemaking[n][dcoinssize - 1]; 34

#include<stdio.h>

#include<string>

int possiblewayschangeorder(int changemakingcoinorder[], int dcoinssize, int n);

int main()

{

    int denominationcoins[] = {1, 3, 5};

    int dcoinssize = sizeof(denominationcoins) / sizeof(denominationcoins[0]);

    int n = 9;

    printf("%d", possiblewayschangeorder(denominationcoins, dcoinssize, n));

    return 0;

}

int possiblewayschangeorder(int changemakingcoinorder[], int dcoinssize, int n)

{

    int coin, making;

    int changemaking[n + 1][dcoinssize];

    for (int i = 0; i < dcoinssize; i++)

        changemaking[0][i] = 1;

    for (int i = 1; i < n + 1; i++)

    {

        for (int j = 0; j < dcoinssize; j++)

        {

            coin = (i - changemakingcoinorder[j] >= 0) ? changemaking[i - changemakingcoinorder[j]][j] : 0;

            making = (j >= 1) ? changemaking[i][j - 1] : 0;

            changemaking[i][j] = coin + making;

        }

    }

    return changemaking[n][dcoinssize - 1];

}\

PLEASE LIKE IT RAISE YOUR THUMBS UP
IF YOU ARE HAVING ANY DOUBT FEEL FREE TO ASK IN COMMENT SECTION