Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Dynamic Programming - Minimum number of coins in C

I have looked through various questions on the site and I haven't managed to find anything which implements this by the following reasoning (so I hope this isn't a duplicate).

The problem I'm trying to solve via a C program is the following:

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.

After looking around online to find how others have solved it, I found the following example applied with pennies, nickels and dimes:

enter image description here

Which I tried to base my code upon. But first of all, my code isn't halting, and secondly, I'm not sure if I'm incorporating the caching element mentioned in the rubric above. (I'm not really sure how I need to go about that part).

Can anyone help find the flaws in my code?

#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 -1;
    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((i>=0) && (a[i]< min))
            min = a[i];
    }
    return min;
}

Any assistance will be greatly appreciated.

like image 898
Luke Collins Avatar asked Feb 03 '16 12:02

Luke Collins


People also ask

What is the formula for calculating the minimum number of coins?

So, we create a minCoins array - minCoins[sum+1] where minCoins[i] represents minimum number of coins required to make change for amount = i. We build up the array in bottom up manner starting with minCoins[0]. The time complexity of the Dynamic Programming solution is O(n*sum). The space complexity is O(sum).

What is the minimum number of coins that must be turned over?

Explanation: Minimum 4 coins required.

What is the minimum number of coins required to achieve a sum of 10?

But, the optimal answer is two coins {3,3}. Similarly, four coins {4,4,1,1} will be selected to make a sum of 10. But, the optimal answer is three coins {4,3,3}.

Does the greedy algorithm find the solution that uses the smallest number of coins possible?

Solution: Greedy Approach. Approach: A common intuition would be to take coins with greater value first. This can reduce the total number of coins needed. Start from the largest possible denomination and keep adding denominations while the remaining value is greater than 0.


1 Answers

OP's supplied Change() algorithm incurs lots of recursion, even with the if(v < 0) return INT_MAX; correction. So much recursion that even small-ish values take millions of recursive calls.

A simple improvement is to "cache" the best solution found so far. Then when an intermediate solution is already worse than the best, no need to continue that path.

int computeChange(int cur[], int v, int n, int count_now, int *bestcount) {
  if (count_now >= *bestcount) {
    return INT_MAX;
  }
  if (v < 0) {
    return INT_MAX;
  }
  if (v == 0) {
    *bestcount = count_now;
    return 0;
  }

  int min_count = INT_MAX;
  for (int i = 0; i < n; i++) {
    int count = computeChange(cur, v - cur[i], n, count_now+1, bestcount);
    if (count < min_count) {
      min_count = count + 1;
    }
  }
  return min_count;
}

  int bc = INT_MAX;
  computeChange(cur, v, n, 0, &bc));

A secondary improvement is to attempt using large coins first

 // int count = computeChange(cur, v - cur[i], n, count_now+1, bestcount);
 int count = computeChange(cur, v - cur[n-i-1], n, count_now+1, bestcount);
like image 196
chux - Reinstate Monica Avatar answered Oct 30 '22 10:10

chux - Reinstate Monica