I wrote a simple coin change algorithm that currently finds the minimum number of coins needed to match the amount required to buy something. I'm trying to modify it so that it keeps track of the minimum number of coins of each denomination to be used and I'm falling a bit short. So, if you were to pass the number 6 to the function, it would say that the minimum number of coins needed is 2 (I already have that down) and that the combination of coins to do so is a 4 cent coin and a 2 cent coin. Here's my code:
coins[5] = {1, 2, 4, 17, 28} //effectively kills any use of greedy algortihms
count[m];
int coins_needed_for(int m) {
//Initilization- fills array w/ -1s
for (int z = 1; z < m+1; z++) {
count[z] = -1;
}//for
//fills in appropriate values
for (int j = 0; j < 5; j++) {
if (coins[j] < m)
count[coins[j]] = 1;
else if (coins[j] == 1)
return 1;
else
break;
}//for
//Execution
for (int p = 1; p < m+1; p++) {
if (count[p] == -1) {
int min = 10000 //poor subsitute for infinity;
for (int i = 0; i < 5; i++) {
if (coins[i] <= p) {
if (count[p-coins[i]] + 1 < min) {
min = count[p-coins[i]] + 1;
}
}//if
count[p] = min;
}//for
}//if
}//for
return count[m];
}
I understand what is required, I'm just not sure what the best way is to go about doing it. Should I create another array, and if so, would it have to be two dimensional? Could I create a struct that keeps count of each coin is used for each possible m? I'm open to any suggestions. I'm not necessarily looking for a definite answer, just pointers and helpful advice. Asking for an answer for an assigned problem is just wrong. Thanks!
This is a very old problem known as the "Change-making problem." See what Wikipedia has to say about it.
It's a form of the knapsack problem, which is not a trivial problem.