A recursive algorithm to find the number of distinct quantities of money from a pile of coins

Question

Problem: find the number of distinct quantities of money that a pile of coins can make.

The vector coins contains the values of the coins, and the corresponding vector quantity contains the number of coin there are (let's say coins = {1} and quantity = {5}, this means I have 5 pennies).

Although I have solved this problem, I would like to make it more time efficient. Could someone give me some pointers?

Miscellaneous info: the variable ctq stands for "coins to quantity". I solved this by systematically iterating through all possible combinations of coins and putting their sum into a set. There has to be a better way to solve this problem, because this problem is supposed to be a dynamic programming question and I solved this problem without any knowledge of what that's supposed to be.

#include<iostream>
#include<vector>
#include<map>
#include<set>

int money(std::map<int, int> x)
{
    int sum=0;
    for(auto it=x.begin(); it!=x.end(); ++it)
    {
        sum+=it->first*it->second;
    }
    return sum;
}

int rec
(
    std::set<int> &sums,
    std::map<int, int> ctq,
    std::vector<int> coins,
    std::vector<int> quantity,
    int m
)
{
    for(int k=quantity[m]; k>=0; k--)
    {
        ctq[coins[m]] = k;
        sums.insert(money(ctq));
        if(m != 0)
        {
            rec(sums, ctq, coins, quantity, m-1);
        }
    }
    return sums.size()-1;
}

int possibleSums(std::vector<int> coins, std::vector<int> quantity)
{
    std::map<int, int> ctq;
    for(std::size_t i=0; i<coins.size(); i++)
    {
        if(ctq.find(coins[i]) == ctq.end())
        {
            ctq.insert(std::make_pair(coins[i], quantity[i]));
        }
        else
        {
            ctq[coins[i]] += quantity[i];
        }
    }

    std::vector<int> n_coins, n_quantity;
    for(auto it = ctq.begin(); it != ctq.end(); ++it)
    {
        n_coins.push_back(it->first);
        n_quantity.push_back(it->second);
    }

    std::set<int> sums;
    return rec(sums, ctq, n_coins, n_quantity, n_coins.size()-1);
}

int main()
{
    std::vector<int> coins = {10, 50, 100, 200};
    std::vector<int> quantity = {511, 22, 30, 50};
    std::cout << possibleSums(coins, quantity) << "\n";
    return 0;
}

Answer 1

Instead of calculating each combination recursively, you can build up the list one coinage type at a time. This would involve fewer iterations in the case that any combinations form the same total, and more importantly wouldn't require adding up each combination separately. For example:

std::set<int> sums;
for(int c = 0; c < coins.size(); ++c)
{
    // Include zero on the initial list, but not subsequent ones
    if(sums.empty()) 
    {
        for(int q = 0; q <= quantity[c]; ++q) 
        {
            sums.insert(q * coins[c]);
        }
    }
    else
    {
        std::vector<int> current(sums.begin(), sums.end());
        for(int q = 1; q <= quantity[c]; ++q)
        {
            for(int sum : current) 
            {
                sums.insert(sum + q * coins[c]);
            }
        }
    }
}         

Using a vector instead of a set to accumulate sums (removing duplicates at the end) might be faster, and would eliminate the need for a temporary copy (current). However, it wouldn't eliminate the redundant loops based off the same total, so some measurements would be needed to see which is better.

std::vector<int> sums;
for(int c = 0; c < coins.size(); ++c)
{
    // Include zero on the initial list, but not subsequent ones
    if(sums.empty()) 
    {
        for(int q = 0; q <= quantity[c]; ++q) 
        {
            sums.push_back(q * coins[c]);
        }
    }
    else
    {
        int oldSize = sums.size();
        for(int q = 1; q <= quantity[c]; ++q)
        {
            for(int i = 0; i < oldSize; ++i) 
            {
                sums.push_back(sums[i] + q * coins[c]);
            }
        }
    }
}  

std::sort(sums.begin(), sums.end());
sums.erase(std::unique(sums.begin(), sums.end()), sums.end());

Answer 2

You already have a good review of the algorithm; I'll just look at the implementation here.

---

Representation

A pair of corresponding containers is more error-prone to use than a container of pairs. Prefer to keep related data together.

In this case, what we have is a bag (aka multiset), which might be best represented as a map from denomination to count.

Pass by reference

Don't pass large objects by value unless you really need a copy. It seems that x, coins and quantity can all be passed as reference to const (this change alone reduced my run times by over 50%).

Loops

Unless you're stuck with C++03, the loops can be made clearer (and therefore less error-prone) by using range-based for. For example:

int money(const std::map<int, int>& x)
{
    int sum=0;
    for (auto const& element: x) {
        sum += element.first * element.second;
    }
    return sum;
}

With a structured binding (since C++17), the intent can be clearer:

    for (auto const [denomination, quantity]: x) {
        sum += denomination * quantity;
    }

You will find that a container-of-pairs representation lends itself better to range-based for, as we don't need to track corresponding indexes.

Let operator[] create entries

This code looks to me like unnecessary work:

    if(ctq.find(coins[i]) == ctq.end())
    {
        ctq.insert(std::make_pair(coins[i], quantity[i]));
    }
    else
    {
        ctq[coins[i]] += quantity[i];
    }

If coins[i] isn't present in ctq, then simply accessing ctq[coins[i]] will do exactly what we need: create an entry with a default-initialised value (i.e. 0). So we can simplify that if/else to just:

    ctq[coins[i]] += quantity[i];

Consider using unsigned types

Since coin denominations and quantities can't be negative, an unsigned type may be more appropriate. That would double the range that you can represent (the current input set isn't in imminent danger of exceeding INT_MAX - which must be at least 32767 - but it wouldn't take much to overstep that mark).

Explain corrective factors

Here, we have a correction of -1:

return sums.size()-1;

It's my guess that the -1 is because we don't consider 0 to be one of the valid results to be counted. It would be worthwhile to have a comment to confirm that guess (or to provide the correct explanation if I'm wrong).