PHP Minimum # Coins for Dollar Amount - Example

AceInfinity · Nov 1, 2013

Code:

[NO-PARSE]#include <iostream>
#include <map>

bool keyComp(unsigned lch, unsigned rch) { return lch > rch; }

typedef std::pair < std::string, size_t > coin_def;
typedef std::map<size_t, coin_def, bool(*)(size_t, size_t)> coin_map;

const size_t TOONIE = 200;
const size_t LOONIE = 100;
const size_t QUARTER = 25;
const size_t DIME = 10;
const size_t NICKEL = 5;
const size_t PENNY = 1;

void CoinsRequired(double amt, coin_map& coinMap)
{
	size_t pennySum = amt * 100;
	for (const auto &it : coinMap)
	{
		size_t count = 0;
		while (pennySum >= count + it.first)
		{
			count += it.first;
			coinMap[it.first].second++;
		}
		pennySum -= count;
	}
}


int main(void)
{
	double amt = 2.37;
	coin_map coinMap(keyComp);
	coinMap.insert(std::pair < size_t, coin_def >(QUARTER, coin_def("Quarter(s)", 0)));
	coinMap.insert(std::pair < size_t, coin_def >(DIME, coin_def("Dime(s)", 0)));
	coinMap.insert(std::pair < size_t, coin_def >(NICKEL, coin_def("Nickel(s)", 0)));
	coinMap.insert(std::pair < size_t, coin_def >(PENNY, coin_def("Penny/Pennies", 0)));
	CoinsRequired(amt, coinMap);

	// Output resules
	std::cout << "Minimum Coin Sums for: $" << amt << std::endl;
	for (const auto &it : coinMap)
	{
		std::cout.width(15);
		std::cout << std::left << it.second.first << ": ";
		std::cout << std::right << it.second.second << std::endl;
	}
}[/NO-PARSE]

Just a simple example I wrote for finding the minimum number of coins possible to make a sum amount (dollar value). May be useful to share it here as well.

Could change it to this as well to allow both double and an integer type of input for the penny amount:

Code:

template <typename T>
void CoinsRequired(T amt, coin_map& coinMap)
{
   T pennySum = amt;
   for (const auto &it : coinMap)
   {
      T count = 0;
      while (pennySum >= count + it.first)
      {
         count += it.first;
         coinMap[it.first].second++;
      }
      pennySum -= count;
   }
}

void CoinsRequired(double amt, coin_map& coinMap)
{
   CoinsRequired((size_t) amt * 100, coinMap);
}[/NO-PARSE][/code]

If I didn't go with the incremental method, I would've used fmod() if dealing with floating point, or just the regular modulo operator for integers. Floating point is okay, but not precise. I'd liked to have used a library like GMP if I took this code more seriously.

*EDIT: Just realized those type params should be updated behind the typedefs as well. Easy fix though... And this is C++11 btw too. :) 

:beerchug2:

AceInfinity · Nov 2, 2013

Just because I was bored:

Code:

#include <iostream>
#include <map>

bool keyComp(unsigned lch, unsigned rch) { return lch > rch; }

template <typename T = size_t>
using coin_def = std::pair < std::string, T >;

template <typename T = size_t>
using coin_map = std::map<T, coin_def<T>, bool(*)(T, T)>;

const size_t TOONIE = 200;
const size_t LOONIE = 100;
const size_t QUARTER = 25;
const size_t DIME = 10;
const size_t NICKEL = 5;
const size_t PENNY = 1;

template <typename T = size_t>
void CoinsRequired(T amt, coin_map<T>& coinMap)
{
	T pennySum = amt;
	for (const auto &it : coinMap)
	{
		T count = 0;
		while (count + it.first <= pennySum)
		{
			count += it.first;
			coinMap[it.first].second++;
		}
		pennySum -= count;
	}
}

void CoinsRequired(double amt, coin_map<size_t>& coinMap) { CoinsRequired<size_t>((size_t) (amt * 100), coinMap); }

typedef std::pair < size_t, coin_def<size_t> > coin_pair;

int main(void)
{
	double amt = 2.37;
	coin_map<size_t> coinMap(keyComp);
	coinMap.insert(coin_pair(QUARTER, coin_def<size_t>("Quarter(s)", 0)));
	coinMap.insert(coin_pair(DIME, coin_def<size_t>("Dime(s)", 0)));
	coinMap.insert(coin_pair(NICKEL, coin_def<size_t>("Nickel(s)", 0)));
	coinMap.insert(coin_pair(PENNY, coin_def<size_t>("Penny/Pennies", 0)));

	CoinsRequired(amt, coinMap);

	// Output resules
	std::cout << "Minimum Coin Sums for: $" << amt << std::endl;
	for (const auto &it : coinMap)
	{
		std::cout.width(15);
		std::cout << std::left << it.second.first << ": ";
		std::cout << std::right << it.second.second << std::endl;
	}
}

But this still doesn't fix the fact that I'm using double as normal/before. This is still an iterative method too. The other way would be to use modulus operations.

Search

Search

PHP Minimum # Coins for Dollar Amount - Example

AceInfinity

Emeritus, Contributor

AceInfinity

Emeritus, Contributor