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 callComputeChange()
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.
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).
Explanation: Minimum 4 coins required.
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}.
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.
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);
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With