#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

void makeChange(vector<int>, int price);
void optimalCoins(vector<int>, vector< vector<int> >, int, int);

int main()
{
    int price, num, val;
    vector<int> mycoins;

    mycoins.push_back(1);

    cout << "A coin with a demonination of '1' has already been added. \n" << "How many coin values would you like to enter? ";
    cin >> num;
    cout << endl << "Please enter " << num << " coin values:\n";

    // get input
    for (int index = 0; index < num; index++) {
        cin >> val;
        if (val != 1) {mycoins.push_back(val);}  // insert val into our vector of coins
    }


    cout << endl << "How many cents would you like change for? ";
    cin >> price;

    sort(mycoins.begin(), mycoins.end()); // sort mycoins from smallest to largest value

    makeChange(mycoins, price); // call the make change function using the mycoin vector and price given

}

/*
    This function creates a True/False matrix using multidimensional vectors
    to determine which coins will be used to create change in the most efficient
    way possible for the given amount.
*/
void makeChange(vector<int> mycoins, int price)
{
    int amount;
    int n = mycoins.size() - 1;
    vector< vector<int> > min, used;

    // initialize all previous amounts
    for (amount = 0; amount <= price; amount++) {
        min[n][amount] = amount;
        used[n][amount] = true;
    }

    for (int index = n - 1; n >= 1; n--) {

        for (amount = 0; amount <= price; amount++) {

            if (mycoins[index] > amount || min[index+1][amount] < 1 + min[index][amount - mycoins[index]]) {
                min[index][amount] = min[index+1][amount];
                used[index][amount] = false;
            }

            else {
                min[index][amount] = 1 + min[index][amount - mycoins[index]];
                used[index][amount] = true;
            }
        }
    }

    optimalCoins(mycoins, used, 0, price);

}

void optimalCoins(vector<int> mycoins, vector< vector<int> > used, int index, int amount) {

    if (amount == 0)
        return;

    if (used[index][amount]) {
        cout << "Coin of Denomination " << mycoins[index] << " used.\n";
        optimalCoins(mycoins, used, index + 1, amount - mycoins[index]);
    }

    else {
        optimalCoins(mycoins, used, index + 1, amount);
    }
}