#include <iostream>
#include <vector>
using namespace std;

/*
 * Dynamic programming algorithm to solve change-making problem.
 * As a result, the coinsUsed array is filled with the
 * minimum number of coins needed for change from 0->maxChange
 * and lastCoin contains one of the coins needed to make the change.
 */
void makeChange( const vector<int> & coins, int maxChange,
                       vector<int> & coinsUsed, vector<int> & lastCoin )
{
    int differentCoins = coins.size( );
    coinsUsed.resize( maxChange + 1 );
    lastCoin.resize( maxChange + 1 );

    coinsUsed[ 0 ] = 0; lastCoin[ 0 ] = 1;

    for( int cents = 1; cents <= maxChange; cents++ )
    {
        int minCoins = cents, newCoin = 1;

        for( int j = 0; j < differentCoins; j++ )
        {
            if( coins[ j ] > cents )   // Can't use coin j
                continue;
            if( coinsUsed[ cents - coins[ j ] ] + 1 < minCoins )
            {
                minCoins = coinsUsed[ cents - coins[ j ] ] + 1;
                newCoin  = coins[ j ];
            }
        }

        coinsUsed[ cents ] = minCoins;
        lastCoin[ cents ]  = newCoin;
    }
}


// Simple test program
int main( )
{
        // The coins and the total amount of change
    vector<int> coins;
    coins.push_back( 1 );
    coins.push_back( 5 );
    coins.push_back( 10 );
    coins.push_back( 21 );
    coins.push_back( 25 );

    vector<int> used;
    vector<int> last;

    for( int change = 4; change < 100; change += 3 )
    {
        makeChange( coins, change, used, last );

        cout << "Total cents: " << change << "; Best is " << used[ change ]  << ": ";

        for( int i = change; i > 0; i -= last[ i ] )
            cout << last[ i ] << " ";
        cout << endl;
    }

    return 0;
}