Divisible by Set

Given some arbitrary set of coins, e.g. { 25, 10, 5 }, and some target currency like 10.46, determine if it is possible to produce the target amount with the set of coins. Assume you have an infinite set of the provided coins.

Method 1, Brute Force

• Check every single possible combination (with duplicates) of coin that can produce it. That is, iterate DFS style, until the final target coin is found.

• Consider the example with set coins 25, 30, 35, with a trivial target of 46.

// assume US currency e.g. $10.99
int convert_to_cents(double number) 
{
    double non_fraction;
    double frac = modf(number, &non_fraction);

    return (100 * non_fraction) + round(frac * pow(10, 2));
}


bool isProperCoinAmount2(int target, unordered_set<int> &setCoins) {
    if (target < 0)
        return false;
    if (target == 0)
        return true;
    if (setCoins.find(target) != setCoins.end())
        return true;

    for (auto &coin : setCoins) {
        if (target > coin) {
            target = target - coin;
            if (isProperCoinAmount2(target, setCoins))
                return true;
        }
    }

    return false;
}


bool isDivisablebySet(double target, unordered_set<int> &setCoins) {
    /*  grab decimal part  */
    int target2 = convert_to_cents(target);
    cout << "coins: " << target2 << endl;

    return isProperCoinAmount2(target2, setCoins);
}

int main() {

    double target = .46;

    unordered_set<int> setCoins = { 25, 10, 5 };
    cout << boolalpha << isDivisablebySet(target, setCoins);
    return 0;
}

Method 2: Dynamic Programming

• This problem clearly has 'optimal substructure', or in other words, inherits overlapping subproblems with brute force approach. If we map for ourselves what doesnt work, and look it up later, we avoid having to descend down the same path again.

• Consider the instance with a set coin amount of {7, 8, 3, 6}, and a target currency of 18 that contains an overlapping subtree of 5.

• We two instances of subtree "5", from which could have been avoided using dp.

// assume US currency e.g. $10.99
int convert_to_cents(double number) 
{
    double non_fraction;
    double frac = modf(number, &non_fraction);

    return (100 * non_fraction) + round(frac * pow(10, 2));
}


bool isProperCoinAmount2(int target, unordered_set<int> &setCoins, unordered_set<int> &memio_map) {
    if (memio_map.find(target) != memio_map.end()) return false;

    if (target < 0) {
        memio_map.insert(target);
        return false;
    }

    if (target == 0)
        return true;
    if (setCoins.find(target) != setCoins.end())
        return true;

    for (auto &coin : setCoins) {
        if (target > coin) {
            target = target - coin;
            if (isProperCoinAmount2(target, setCoins, memio_map))
                return true;
        }
    }

    return false;
}


bool isDivisablebySet(double target, unordered_set<int> &setCoins) {
    int target2 = convert_to_cents(target);
    cout << "coins: " << target2 << endl;

    return isProperCoinAmount2(target2, setCoins, unordered_set<int>());
}


int main() {

    double target = 4.58;

    unordered_set<int> setCoins = { 25, 10, 5 };
    cout << boolalpha << isDivisablebySet(target, setCoins);
    return 0;
}