How can I add limited coins to the coin change problem? (Bottom-up - Dynamic programming)

Question

I am new to dynamic programming (and C++ but I have more experience, some things are still unknown to me). How can I add LIMITED COINS to the coin change problem (see my code below - is a bit messy but I'm still working on it). I have a variable nr[100] that registers the number of coins (also created some conditions in my read_values() ). I don't know where can I use it in my code.

The code considers that we have an INFINITE supply of coins (which I don't want that). It is made in the bottom-up method (dynamic programming).

My code is inspired from this video: Youtube

#include <iostream>
using namespace std;
int C[100], b[100], n, S, s[100], nr[100], i, condition=0, ok=1;

void read_values() //reads input
{   
    cin >> n; // coin types
    cin >> S; // amount to change
    
    for (i=1; i<=n; i++)
    {
        cin >> b[i]; //coin value
        cin>>nr[i]; //coin amount
        if(nr[i]==0)b[i]=0; //if there are no coin amount then the coin is ignored
        
        condition+=b[i]*nr[i]; //tests to see if we have enough coins / amount of coins to create a solution
        if(b[i]>S)
        {
            b[i]=0;
        }
    }

    if(S>condition)
    {
        cout<<endl;
        cout<<"Impossible!";
        ok=0;
    }
}
void payS()
{
    int i, j;
    C[0] = 0; // if amount to change is 0 then the solution is 0
    for (j=1; j<=S; j++) 
    {
        C[j] = S+1;
        for (i=1; i<=n; i++)
        {

            if (b[i] <= j && 1 + C[j - b[i]] < C[j])
            {
                C[j] = 1 + C[j - b[i]]; 
                s[j] = b[i];
            }

        }
    }
    cout << "Minimum ways to pay the amount: " << C[S] << endl;
}

void solution(int j)
{
    if (j > 0)
    {
        solution(j - s[j]);
        cout << s[j] << " ";
    }
}
int main()
{

    read_values();
    if(ok!=0)
    {
        payS();
        cout << "The coins that have been used are: ";
        solution(S);
    }
}

Answer 1

I'm working under the assumption that you need to generate change for a positive integer value, amount using your nbr table where nbr[n] is the number of coins available of value n. I'm also working under the assumption that nbr[0] is effectively meaningless since it would only represent coins of no value.

Most dynamic programming problems are typically recursing on a binary decision of choosing option A vs option B. Often times one option is "pick this one" and other is "don't pick this one and use the rest of the available set". This problem is really no different.

First, let's solve the recursive dynamic problem without a cache.

I'm going to replace your nbr variable with a data structure called a "cointable". This is used to keep track of both the available set of coins and the set of coins selected for any given solution path:

struct cointable
{
    static const int MAX_COIN_VALUE = 100;
    int table[MAX_COIN_VALUE+1]; // table[n] maps "coin of value n" to "number of coins availble at amount n"
    int number; // number of coins in table
};

cointable::table is effectively the same thing as your nbr array. coinbase::number is the summation of the values in table. It's not used to keep track of available coins, but it is used to keep track of the better solution.

Now we can introduce the recursive solution without a lookup cache.

Each step of the recursion does this:

1. Look for the highest valuable coin that is in the set of available coins not greater than the target amount being solved for

2. Recurse on option A: Pick this coin selected from step 1. Now solve (recursively) for the reduced amount using the reduced set of available coins.

3. Recurse on option B: Don't pick this coin, but instead recurse with the first coin of lesser value than what was found in step 1.

4. Compare the recursion results of 2 and 3. Pick the one with lesser number of coins used

Here's the code - without using an optimal lookup cache

bool generateChange(int amount, cointable& available, cointable& solution, int maxindex)
{
    if ((maxindex == 0) || (amount < 0))
    {
        return false;
    }

    if (amount == 0)
    {
        return true;
    }

    int bestcoin = 0;

    // find the highest available coin that not greater than amount
    if (maxindex > amount)
    {
        maxindex = amount;
    }

    // assert(maxindex <= cointable::MAX_COIN_VALUE)

    for (int i = maxindex; i >= 1; i--)
    {
        if (available.table[i] > 0)
        {
            bestcoin = i;
            break;
        }
    }

    if (bestcoin == 0)
    {
        return false; // out of coins
    }

    // go down two paths - one with picking this coin.  Another not picking it

    // option 1
    // pick this coin (clone available and result)
    cointable a1 = available;
    cointable r1 = solution;
    a1.table[bestcoin]--;
    r1.table[bestcoin]++;
    r1.number++;
    bool result1 = generateChange(amount - bestcoin, a1, r1, bestcoin);

    // option2 - don't pick this coin and start looking for solutions with lesser 
    // coins (not the use of references for a2 and r2 since we haven't changed anything)

    cointable& a2 = available;
    cointable& r2 = solution;
    bool result2 = generateChange(amount, a2, r2, bestcoin - 1);

    bool isSolvable = result1 || result2;

    if (!isSolvable)
    {
        return false;
    }

    // note: solution and r2 are the same object, no need to reassign solution=r2
    if (
        ((result1 && result2) && (r1.number < r2.number))
        || (result2 == false)
        )
    {
        solution = r1;
    }

    return true;
}

And then a quick demonstration for how to calculate change for 128 cents given a limited amount of coins in the larger denominations: {1:100, 5:20, 10:10, 25:1, 50:1}

int main()
{
    cointable available = {};  // zero-init
    cointable solution = {};   // zero-init

    available.table[1] = 100;
    available.table[5] = 20;
    available.table[10] = 10;
    available.table[25] = 1;
    available.table[50] = 1;
    int amount = 128;

    bool result = generateChange(amount, available, solution, cointable::MAX_COIN_VALUE);

    if (result == true)
    {
        for (int i = 1; i < 100; i++)
        {
            if (solution.table[i] > 0)
            {
                std::cout << i << " : " << solution.table[i] << "\n";
            }
        }
    }
    else
    {
        cout << "no solution\n";
    }
}

And that should work. And it might be fast enough for most making change for anything under a dollar such that a cache is not warranted. So it's possible we can stop right here and be done.

And I am going to stop right here

I started to work on a solution that introduces a "cache" to avoid redundant recursions. But after benchmarking it and studying how the algorithm finds the best solution quickly, I'm not so sure a cache is warranted. My initial attempt to insert a cache table for both solvable and unsolvable solutions just made the code slower. I'll need to study how to make it work - if it's even warranted at all.

Answer 2

Maybe you wanted us to fix your code, but instead I implemented my own version of solution. Hopefully my own version will be useful somehow for you, at least educationally.

Of course I used Dynamic Programming approach for that.

I keep a vector of possible to compose changes. Each next sums is composed of previous sums by adding several coins of same value.

History of used coins is also kept, this allows us to restore each change as combination of exactly given coins.

After code you can see console output that shows example of composing change 13 out of coins 2x4, 3x3, 5x2, 10x1 (here second number is amount of coins).

Input coins and their amount is given inside coins vector at start of main() function, you can fill this vector with anything you want, for example by taking console user input. Needed to be represented change is given inside variable change.

Don't forget to see Post Scriptum (PS.) after code and console output, it has some more details about algorithm.

Full code below:

Try it online!

#include <cstdint>
#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <functional>
#include <iostream>

using u32 = uint32_t;
using u64 = uint64_t;

int main() {
    std::vector<std::pair<u32, u32>> const coins =
        {{2, 4}, {3, 3}, {5, 2}, {10, 1}};

    u32 const change = 13;

    std::vector<std::unordered_map<u32, std::pair<u64, std::set<u32>>>>
        sums = {{{0, {1, {}}}}};

    for (auto [coin_val, coin_cnt]: coins) {
        sums.push_back({});
        for (auto const & [k, v]: sums.at(sums.size() - 2))
            for (size_t icnt = 0; icnt <= coin_cnt; ++icnt) {
                auto & [vars, prevs] = sums.back()[k + coin_val * icnt];
                vars += v.first;
                prevs.insert(icnt);
            }
    }
    std::vector<std::pair<u32, u32>> path;
    std::vector<std::vector<std::pair<u32, u32>>> paths;
    std::function<bool(u32, u32, u32)> Paths =
        [&](u32 sum, u32 depth, u32 limit){
            if (sum == 0) {
                paths.push_back(path);
                std::reverse(paths.back().begin(), paths.back().end());
                return paths.size() < limit;
            }
            auto const coin = coins.at(depth - 1).first;
            auto const & [_, prevs] = sums.at(depth).at(sum);
            for (auto const cnt: prevs) {
                if (cnt > 0)
                    path.push_back({coin, cnt});
                if (!Paths(sum - coin * cnt, depth - 1, limit))
                    return false;
                if (cnt > 0)
                    path.pop_back();
            }
            return true;
        };

    if (!sums.back().count(change)) {
        std::cout << "Change " << change
            << " can NOT be represented." << std::endl;
        return 0;
    }
    std::cout << "Change " << change << " can be composed "
        << std::get<0>(sums.back().at(change)) << " different ways." << std::endl;
    Paths(change, coins.size(), 20);
    std::cout << "First " << paths.size() << " variants:" << std::endl;
    for (auto const & path: paths) {
        std::cout << change << " = ";
        for (auto [coin, cnt]: path)
            std::cout << coin << "x" << cnt << " + ";
        std::cout << std::endl;
    }
}

Output:

Change 13 can be composed 5 different ways.
First 5 variants:
13 = 2x2 + 3x3 + 
13 = 2x4 + 5x1 + 
13 = 2x1 + 3x2 + 5x1 + 
13 = 3x1 + 5x2 + 
13 = 3x1 + 10x1 + 

PS. As you may have noticed, main Dynamic Programming part of algorithm is very tiny, just following lines:

    std::vector<std::unordered_map<u32, std::pair<u64, std::set<u32>>>>
        sums = {{{0, {1, {}}}}};

    for (auto [coin_val, coin_cnt]: coins) {
        sums.push_back({});
        for (auto const & [k, v]: sums.at(sums.size() - 2))
            for (size_t icnt = 0; icnt <= coin_cnt; ++icnt) {
                auto & [vars, prevs] = sums.back()[k + coin_val * icnt];
                vars += v.first;
                prevs.insert(icnt);
            }
    }

This part keeps all currently composable sums (changes). Algo starts from money change of 0, then incrementally adds 1-by-1 coin to all possible current changes (sums), thus forming new sums (including this new coin).

Each sum keeps a counter of all possible ways to compose it plus it keeps track of all last coins that lead to this sum. This last coins set allows to do back-tracking in order to restore concrete combinations of coins, not just amount of ways to compute this sum.