Making Change | C++ Implementation Implement a Dynamic Programming change algori

Question

Making Change | C++ Implementation

Implement a Dynamic Programming change algorithm. The program should read input from a file named “amount.txt”. The file contains lists of denominations (V) followed on the next line by the amount A.
Example amount.txt:
1 2 5
10
1 3 7 12
29
1 2 4 8
15

In the above example the first line contains the denominations V=(1, 2, 5) and the next line contains the amount A = 10 for which we need change. There are three different denomination sets and amounts in the above example. A denomination set will be on a single line and will always start with the 1 “coin”.

The results should be written to a file named change.txt and should contain the denomination set, the amount A, the change result array and the minimum number of coins used.
Example change.txt:
125
10
0 0 2
2
1 3 7 12
29
0 1 2 1
4
1 2 4 8
15
1 1 1 1
4
In the above example, to make 29 cents change from the denomination set (1, 3, 7, 12) you need 0: 1 cent coin, 1: 3 cent coin, 2: 7 cent coins and 1: 12 cent coin for a total of 4 coins.

Explanation / Answer

#include<stdio.h>

// Returns the count of ways we can sum S[0...m-1] coins to get sum n

int count( int S[], int m, int n )

{

    // If n is 0 then there is 1 solution (do not include any coin)

    if (n == 0)

        return 1;

    // If n is less than 0 then no solution exists

    if (n < 0)

        return 0;

    // If there are no coins and n is greater than 0, then no solution exist

    if (m <=0 && n >= 1)

        return 0;

    // count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]

    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );

}

// Driver program to test above function

int main()

{

    int i, j;

    int arr[] = {1, 2, 3};

    int m = sizeof(arr)/sizeof(arr[0]);

    printf("%d ", count(arr, m, 4));

    getchar();

    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

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