make_change.cc

#include <iostream>
#include <vector>

int32_t make_change(const std::vector<int32_t> &denominations,
                     const int32_t &amount,
                     std::vector<int32_t> &coin_count,
                     std::vector<int32_t> &coins_used) {
  for (int32_t i = 0; i < amount + 1; ++i) {
    int32_t count = i;
    int32_t new_coin = 1;
    std::vector<int32_t> smaller_denominations;

    for (const auto &it : denominations) {
      if (it <= i) { smaller_denominations.push_back(it); }
    }

    for (const auto &j : smaller_denominations) {
      if (coin_count[i - j] + 1 < count) {
        count = coin_count[i - j] + 1;
        new_coin = j;
      }
    }

    coin_count[i] = count;
    coins_used[i] = new_coin;
  }

  return coin_count[amount];
}

void print_coins(const std::vector<int32_t> &coins_used, const int32_t &amount) {
  int32_t coin = amount;
  while (coin > 0) {
    int32_t current_coin = coins_used[coin];
    std::cout << current_coin << std::endl;
    coin -= current_coin;
  }
}

int main() {
  const int32_t amount = 63;
  std::vector<int32_t> denominations = { 1, 5, 10, 21, 25 };
  std::vector<int32_t> coin_count;
  std::vector<int32_t> coins_used;
  coin_count.reserve(amount + 1);
  coins_used.reserve(amount + 1);
  for (int32_t i = 0; i < amount + 1; ++i) {
    coin_count.push_back(0);
    coins_used.push_back(0);
  }

  std::cout << "Making change for " << amount << " requires" << std::endl;
  std::cout << make_change(denominations, amount, coin_count, coins_used);
  std::cout << " coins" << std::endl;
  std::cout << "They are:" << std::endl;
  print_coins(coins_used, amount);
  std::cout << "The used list is as follows:" << std::endl;
  std::cout << "[";
  for (int32_t i = 0; i < coins_used.size() - 1; ++i) {
    std::cout << coins_used[i] << ", ";
  }
  std::cout << coins_used[coins_used.size() - 1] << "]" << std::endl;

  return 0;
}