Denominate the amount with the minimum number of coins with a given face value. Greedy problem

Question

I have the C++ function to do. It works fine, but there are some cases where it works bad - "greedy problem".

My C++ code:

#include <vector>
#include <algorithm>

std::vector<int> ans;

std::vector<int> get_change(const std::vector<int> &denominations, int amount) {
    //pure algo
    std::vector<int> money = denominations;
    std::vector<int> count;
    ans.clear();
    count.assign(money.size(), 0);
    std::sort(money.begin(), money.end());
    int summ = amount;
    for (int i = count.size()-1; i >= 0; i--) {
        count[i] = summ / money[i];
        summ = summ % money[i];
        if (summ==0)
            break;
    }


    //ans generation
    for (int i = 0; i < money.size(); i++)
        for (int j = 0; j < count[i]; j++)
            ans.push_back(money[i]);
    return ans;
}

Greedy problem sample: get_change({ 1, 6, 9 }, 30) will return { 1, 1, 1, 9, 9, 9 }, but not { 6, 6, 9, 9 }.

The task is to improve this algorithm to get the same answer.

Answer 1

One possible approach is backtracking.

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. (Wikipedia)

Here, we try to determine the number of coins, for each coin.

The candidates are abandonned, as soon as the total number of coins is higher than the current optimal solution. Moreover, here, in a given situation (at step i), we directly calculate the maximum number of coins for coins[i], such that the total sum is not higher than the amount.

Here is a possible implementation:

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

std::vector<int> get_change(const std::vector<int>& denominations, int amount) {
    std::vector<int> coins = denominations;
    std::vector<int> n_coins(coins.size(), 0);
    std::vector<int> n_coins_opt(coins.size(), 0);
    int n = coins.size();

    std::sort(coins.begin(), coins.end(), std::greater<int>());

    int sum = 0;    // current sum
    int i = 0;      // index of the coin being examined
    int n_min_coins = amount / coins[n - 1] + 1;
    int n_total_coins = 0;
    bool up_down = true;

    while (true) {          // UP
        if (up_down) {
            n_coins[i] = (amount - sum) / coins[i];     // max number of coins[i]
            sum += n_coins[i] * coins[i];
            n_total_coins += n_coins[i];
            if (sum == amount) {
                if (n_total_coins < n_min_coins) {
                    n_min_coins = n_total_coins;
                    n_coins_opt = n_coins;
                }
                up_down = false;
                sum -= n_coins[i] * coins[i];
                n_total_coins -= n_coins[i];
                n_coins[i] = 0;
                i--;
            }
            else {
                if (i == (n - 1) || (n_total_coins >= n_min_coins)) {   // premature abandon
                    sum -= n_coins[i] * coins[i];
                    n_total_coins -= n_coins[i];
                    n_coins[i] = 0;
                    up_down = false;
                    i--;
                }
                else {
                    i++;
                }
            }

        }
        else {            // DOWN
            if (i < 0) break;
            if (n_coins[i] == 0) {
                if (i == 0) break;
                i--;
            }
            else {
                sum -= coins[i];
                n_coins[i] --;
                n_total_coins--;
                i++;
                up_down = true;
            }
        }
    }

    std::vector<int> ans;

    for (int i = 0; i < coins.size(); i++)
        for (int j = 0; j < n_coins_opt[i]; j++)
            ans.push_back(coins[i]);

    return ans;
}

int main() {
    std::vector<int> coins = { 1, 6, 9 };
    int amount = 30;
    auto n_coins = get_change(coins, amount);

    for (int i = 0; i < n_coins.size(); i++)
            std::cout << n_coins[i] << " ";

    std::cout << "\n";
    return 1;
}