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:

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.

回答1:

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);

回答2:

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 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.

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;

}

回答3:

if you have the sum of say x and the coins of denominations say a1, a2, a3, a4..(in decreasing order) then the answer is simply-> x/a1+(x%a2)/a3+((x%a2)%a3)/a4+... This should hopefully give the answer