Dynamic Programming - Minimum Coin caching

Question

Earlier I posted a question about the coin vending machine problem (the minimum number of coins required). Turns out the issue was a typo in a for loop, so now the program works. The original question was this:

As the programmer of a vending machine controller your are required to compute the minimum number of coins that make up the required change to give back to customers. An efficient solution to this problem takes a dynamic programming approach, starting off computing the number of coins required for a 1 cent change, then for 2 cents, then for 3 cents, until reaching the required change and each time making use of the prior computed number of coins. Write a program containing the function ComputeChange(), that takes a list of valid coins and the required change. This program should repeatedly ask for the required change from the console and call ComputeChange() accordingly. It should also make use of “caching”, where any previously computed intermediate values are retained for subsequent look-up.

The issue is that the code makes use of recursion, so it takes quite a long time to evaluate large values. Making use of caching should improve the issue, but I have no idea how to go about it. The code can be found below.

#include <stdio.h>
#include <limits.h>

int computeChange(int[],int,int);
int min(int[],int);

int main(){
    int cur[]={1,2,5,10,20,50,100,200};
    int n = sizeof(cur)/sizeof(int);
    int v;

    printf("Enter a value in euro cents: ");
    scanf("%d", &v);

    printf("The minimum number of euro coins required is %d", computeChange(cur, v, n));

    return 0;
}

int computeChange(int cur[], int v, int n){
    if(v < 0)
        return INT_MAX;
    else if(v == 0)
        return 0;
    else{
        int possible_mins[n], i;
        for(i = 0; i < n; i++){
            possible_mins[i]=computeChange(cur, v-cur[i], n);
        }
        return 1+min(possible_mins, n);
    };
}

int min(int a[], int n){
    int min = INT_MAX, i;
    for(i = 0; i < n; i++){
        if((a[i]>=0) && (a[i]< min))
            min = a[i];
    }
    return min;
}

phoenix phoenix · Accepted Answer · 2016-02-03T17:42:32

With your existing code:

#include <stdio.h>
#include <limits.h>

int computeChange(int[],int,int);
int min(int[],int);
void initChange ();
int change [MAX]; //used for memoization



int main(){
    int cur[]={1,2,5,10,20,50,100,200};
    int n = sizeof(cur)/sizeof(int);
    int v;

    initChange ();
    printf("Enter a value in euro cents: ");
    scanf("%d", &v);

    printf("The minimum number of euro coins required is %d", computeChange(cur, v, n));

    return 0;
}

void initChange () {
    int i =0;
    for (i = 0; i < MAX; i++) {
        change[i] = INT_MAX;
    }
}

int computeChange(int cur[], int v, int n){
    if(v < 0)
        return INT_MAX;
    else if(v == 0)
        return 0;
    else{

        if (change[v] == INT_MAX) {
            int possible_mins[n], i;
            for(i = 0; i < n; i++){
                possible_mins[i]=computeChange(cur, v-cur[i], n);
            }
            change[v] = 1 + min(possible_mins, n); // memoization
        }
        return change[v];//you return the memoized value

    };
}

int min(int a[], int n){
    int min = INT_MAX, i;
    for(i = 0; i < n; i++){
        if((a[i]>=0) && (a[i]< min))
            min = a[i];
    }
    return min;
}

I already posted a solution using loops in your previous question. I will post it again here:

So the below is the code snippet for your problem using memoization and dynamic programming. The complexity is O(Val*numTypesofCoins).

In the end, change[val] will give you the min number of coins for val.

int main (void) {
    int change [MAX];
    int cur[]={1,2,5,10,20,50,100,200};
    int n = sizeof(a)/sizeof(int);
    int val; //whatever user enters to get the num of coins required.
    printf("Enter a value in euro cents: ");
    scanf("%d", &val);

    for (i=0; i <= val; i++) {
        change[i] = INT_MAX;
    }
    for (i=0; i < n; i++) { // change for the currency coins should be 1.
        change[cur[i]] = 1;
    }

    for (i=1; i <= val; i++) {
        int min = INT_MAX;
        int coins = 0;
        if (change[i] != INT_MAX) { // Already got in 2nd loop
            continue;
        }
        for (j=0; j < n; j++) {
            if (cur[j] > i) { // coin value greater than i, so break.
                break;
            }
            coins = 1 + change[i - cur[j]]; 
            if (coins < min) {
                min = coins;
            }
        }
        change[i] = min;

    }
}

Dynamic Programming - Minimum Coin caching

1 Answers