Minimum number of coins - (dynamic programming solution - topdown approach)

Question

This is a problem from topcoder tutorials

Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S.

This is my first attempt at a DP solution. Did I do it right? How to make this code better, faster and less ugly? Is there a better solution than what I did?

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

int coins_td(std::vector<int>& v, int n, std::set<int>& s);

int coins_td(int n, std::set<int>& s) {
    std::vector<int> coins(n+1, -1);
    coins[0] = 0;
    return coins_td(coins, n, s);
}

int coins_td(std::vector<int>& v, int n, std::set<int>& s) {
    static const int coin = 1;
    if (n < 0) {
        return -2;
    }
    if (n == 0) {
        return 0;
    }
    if (v[n] != -1) {
        return v[n];
    }
    int tcoins = coin+coins_td(v, n-*s.begin(), s);
    for (auto i = s.rbegin(); i != s.rend(); ++i) {
        if (n >= *i) {
            tcoins = std::min(tcoins, coin+coins_td(v, n-*i, s));
            break;
        }
    }
    v[n] = tcoins;
    return tcoins;
}

int main() {
    int value;
    std::cin >> value;
    if (value <= 0) {
        std::cout << value << '\n';
    } else {
        std::set<int> values;
        int v;
        while (std::cin >> v) {
            values.insert(v);
        }
        int result = coins_td(value, values);
        if (result == 0) {
            std::cout << "it's not possible to select coins in such a way that they sum up to " << value << "." << '\n';
        } else {
            std::cout << result << '\n';
        }
    }
}

Answer 1

main

    if (value <= 0) {
        std::cout << value << '\n';

This seems to be an error condition. You might consider using std::cerr instead:

        std::cerr << "Value must be positive.  You provided:  " << value << '\n';
        return EXIT_FAILURE;

This also adds an error message so that we don't have to read the code to try to figure out why it is printing a value to the screen.

The explicit return allows us to return something different for the error condition than for a successful run. Once we have it, we can get rid of the else clause and just proceed with the rest of the block.

        if (result == 0) {

I'd tend to make this <= 0 instead. Only positive values are correct. In fact, I might switch the logic around the other way:

    if ( 0 < result ) {
        std::cout << "The minimum number of coins that sum to " << value << " is " << result << ".\n";
    } else {
        std::cout << "It's not possible to select coins in such a way that they sum up to " << value << ".\n";
    }

I find it easier to follow to make the failure case the else (except for an early return as used prior). I also added more of a message in the case of success.

Naming

int coins_td(std::vector<int>& v, int n, std::set<int>& s);

The input is described as a desired sum, S, and a list of coin values, V1..VN. So I would expect a vector named v to refer to that input value. However, in this case, v holds an intermediate result and s holds the coin values. The desired value is in n. It would be reasonable to use the same names as in the problem statement. Normally if you change them, you'd change them to be more descriptive, e.g. desired_sum and coin_values.

What is a coins_td? I've been looking at this problem for some time now, and I still have no idea. It's possible that I'm just being slow, but this suggests to me that it is a non-descriptive name. Writing it out rather than abbreviating might help.

    static const int coin = 1;

While it's good that you're trying to avoid magic numbers in your code, this is a bit confusing. What is coin and why does it equal 1? I actually think that using the value 1 is more obvious about what is happening in this case.

Correctness

for (auto i = s.rbegin(); i != s.rend(); ++i) {
    if (n >= *i) {
        tcoins = std::min(tcoins, coin+coins_td(v, n-*i, s));
        break;
    }
}

This is not correct because it stops at the first one rather than the smallest one. Consider a desired value of 7 with coin values of 1, 3, 4, and 5. This code would return an answer of 3 (for 1+1+5), but the correct answer is 2 (4+3). You should remove the break statement.

    int tcoins = coin+coins_td(v, n-*s.begin(), s);

This is incorrect because it is possible that there may be no way to reach the value n-*s.begin() in which case it will return -1, which will be smaller than any of the correct values. Instead, set it to a number larger than the maximum possible value:

int tcoins = n + 1;

That will make the loop logic work consistently.

    if (n < 0) {
        return -2;
    }

Same thing here. You should return a large number, not a small one. That will also fix the problem of this being a magic number based on the fact that 1 + -2 = -1 where -1 is your magic value for an unset entry in v.

    if (n < 0) {
        return std::numeric_limits<int>::max();
    }

More info on std::numeric_limits. Or leave this off entirely, as in the current code, this should never happen. It only happens in the original code because of initializing tcoins without checking that its possible.

std::vector<int> coins(n+1, -1);

And again here.

    if (n == 0) {
        return 0;
    }
    if (v[n] != -1) {
        return v[n];
    }

These are redundant. Since v[0] = 0, the second if will have the same effect as the first when n == 0.

    if ( v[n] <= n ) {
        return v[n];
    }

Or

    if ( v[n] < std::numeric_limits<int>::max() ) {
        return v[n];
    }

Either should work fine. Note that a valid v[n] can't be greater than n because the coin values are positive integers (or at least I think that they should be).