Modifying the Coin Change problem to keep track of what coin is used (not minimum number)

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.

You can use division and modulus to do it easier. I'll get an example.

afterQuarterTotal = totalAmount % 25; 
numberOfQuarters = (totalAmount - afterQuarterTotal) / 25; 
afterDimeTotal = aftgerQuarterTotal % 10; 
numberOfDimes = (afterQuarterTotal - afterDimeTotal) / 10;

and so on...

void recursive_program(int coins) 

{
    int times;
    if (coins==0)                                                
           return;

if (coins>=28)                                                  
    {                                                             
    times=coins/28;
    cout<<times; 
    cout<<" * 28 for\t\t"<<times*28<<endl;
    return recursive_program(coins%28);
}

if (coins>=17)                                                
{
    times=coins/17;
    cout<<times; 
    cout<<" * 17 for\t\t\t "<<times*17<<endl;
    return recursive_program(coins%17);
}

if (coins>=4)                                                 
{
    times=coins/4;
    cout<<times;
    cout<<" * 4 for\t\t\t "<<times*4<<endl;
    return recursive_program(coins%4);
}
if (coins>=2)                                                 
{
    times=coins/2;
    cout<<times;
    cout<<" * 2 for\t  "<<times*2<<endl;
    return recursive_program(coins%2);
}

if (coins>=1)                                                 
{
    times=coins/1;
    cout<<times;
    cout<<" * 1 for\t\t\t\t  "<<times<<endl;
    coins=0;
    return recursive_program(coins);
}
}

/* Coin Change Problem

Input Specification: First Line expects the amount Second Line expects the number of coins Third Line contains coins in ascending order of denominations Infinite Supply Of Coins is assumed

Ouput Specification: Each case is displayed with the lowest denomination coin first then the next hignest denomination. Cases are separated by lines If sum cannot be found -1 is printed

*/

#include<iostream>
using namespace std;
int *num,*coins,*maxC,n,amount,flag=0,stop=0;
int sum()
{
    int i=0,j;
    int sum=0;
    for(i=0;i<n;++i)
        for(j=0;j<num[i];++j)
            sum+=coins[i];
    return sum;
}
void print()
{
    int i,j;
    for(i=0;i<n;++i)
    {
        for(j=0;j<num[i];++j)
            cout<<coins[i]<<" ";
    }
    cout<<endl;
}
void printNum()
{
    int i;
    for(i=0;i<n;++i)
        cout<<num[i]<<" ";
    cout<<endl;
}
void nextIter()
{
    int i,j;
    int stat=0;
    //printNum();   //Remove the comment if you want to see the values of num array in every iteration
    for(i=0;i<n;++i)
    {
        if(num[i]==0)
            stat=1;
        else
        {
            stat=0;
            break;
        }
    }
    if(stat)
    {
        stop=1;
        return ;
    }
    for(i=n-1;i>=0;--i)
    {
        int dec=0;
        if(num[i]==0)
        {
            dec=1;
            num[i]=maxC[i];
        }
        else
        {
            --num[i];
            return ;
        }
    }
}
int find()
{
    while(!stop)
    {
        if(amount==sum())
        {
            flag=1;
            print();
        }
        nextIter();
    }
}
int main()
{
    int i;
    cout<<"\nEnter amount:";
    cin>>amount;
    cout<<"\nEnter number of coins:";
    cin>>n;
    coins=new int[n];
    maxC=new int[n];//contains maximum number of each denomination required
    num=new int[n];//contains current number of each denomination required
    for(i=0;i<n;++i)
    {
        cin>>coins[i];
        num[i]=maxC[i]=amount/coins[i];
    }
    find();
    if(!flag)
        cout<<"-1";
    cout<<endl;
    system("pause");
    return 0;
}