お釣りの金種を最小にする支払い方

元の記事とは関係ないけどおまけ

金種

紙幣や硬貨の種類のことを金種といいます

金種計算

紙幣や硬貨の種類を考慮した金額の計算のことを金種計算と呼ぶようです

所持金と金額

物の値段はただの数値です
紙幣や硬貨の種類は関係ありません
100円のものを100円玉1枚で買おうと10円玉10枚で買おうと同じですね

所持金はただの数値ではありません
100円玉を 1枚持っているときにそこから10円だけ払うという訳にはいきません
10円のものを買うなら100円玉 1枚を払って90円のお釣りをもらうしかありませんね

お釣り

100円で10円のものを買うと90円のお釣りですが、50円玉 1枚と10円玉 4枚でも 1円玉90枚でも90円は90円です
レジの中にあるお金はただの数値ではなく実在のお金ですから、どのような組み合わせになるかはレジの中にある金種次第ということになりますが、受け取る側からすればお釣りでもらう金種はできるだけ少ない方が好ましいですね

お釣りの金種を最小に

100円玉を 1枚持っているときに 10円のものを買おうとした場合、100円玉を 1枚出す以外に払いようはないわけですが
例えば 2345円（1000円札を 2枚、100円玉を 3枚、10円玉を 4枚、5円玉を 1枚）持っているときに 928円のものを買おうとした場合、1000円を出すと 72円のお釣りになりますが、1030円支払えばお釣りは 102円になります
金額としては 72円より 102円の方が大きくはなりますが、金種としては 72円より 102円の方が少ないのでより好ましいですね

ここではこのように所持金と値段が与えられたときに受け取るお釣りの金種が最小になるような支払い方についてプログラムを書いてみましょう

数値と金種

いちいち 2345円（1000円札を 2枚、100円玉を 3枚、10円玉を 4枚、5円玉を 1枚）などというのは面倒なので、ただ単に 2345円といわれたら最小の金種の組み合わせであるということにしましょう

つまり、1円玉は 4枚まで、5円玉は 1枚まで、10円玉は 4枚まで、50円玉は 1枚まで、100円玉は 4枚まで、500円玉は 1枚まで、1000円札は 4枚まで、5000円札は 1枚までという組み合わせです
10000円札の枚数に制限はありません

準備その１：数値を金種に分解

何にもわからないときは、まずは簡単なところから始めましょう

数値を金種に分解できるでしょうか

上の条件に合うように分解するには上の位の金種から順番に取っていけばよさそうです

const int	c_currency_denominations_jpy[] = { 1, 5, 10, 50, 100, 500, 1000, 5000, 10000 };

void	print_currency( int	currency ){
	OutputDebugStringA( stringprintf( "%d円 {\n", currency ));
	for( size_t	n = 0; n < elementsof( c_currency_denominations_jpy ); ++n ){
		size_t	m = elementsof( c_currency_denominations_jpy ) - n - 1;
		int	d = currency / c_currency_denominations_jpy[m];
		OutputDebugStringA( stringprintf( "\t%5d円 %d枚\n", c_currency_denominations_jpy[m], d ));
		currency %= c_currency_denominations_jpy[m];
	}
	OutputDebugStringA( "}\n" );
}
void	currency_test(){
	print_currency( 123 );
	print_currency( 68 );
	print_currency( 55 );
}
int	main(){
	currency_test();
	return	0;
}

準備その２：金種を考慮せず計算しみる

また所持金と値段と残金の計算はできるでしょうか
こちらもわからなかったらまずは金種は気にせず書いてみましょう

const int	c_currency_denominations_jpy[] = { 1, 5, 10, 50, 100, 500, 1000, 5000, 10000 };

void	print_currency( const char*	prompt_text, int	currency ){
	OutputDebugStringA( stringprintf( "\t%s%d円 {\n", prompt_text, currency ));
	for( size_t	n = 0; n < elementsof( c_currency_denominations_jpy ); ++n ){
		size_t	m = elementsof( c_currency_denominations_jpy ) - n - 1;
		int	d = currency / c_currency_denominations_jpy[m];
		OutputDebugStringA( stringprintf( "\t\t%5d円 %d枚\n", c_currency_denominations_jpy[m], d ));
		currency %= c_currency_denominations_jpy[m];
	}
	OutputDebugStringA( "\t}\n" );
}
int	purchase_test( int	current, int	price ){
	OutputDebugStringA( stringprintf( "%d円あるときに %d円のものを買う {\n", current, price ));
	print_currency( "所持金 ", current );
	int	payment = current;
	print_currency( "支払い ", payment );
	int	change = payment - price;
	print_currency( "お釣り ", change );
	int	result = ( current - payment + change );
	print_currency( "残り ", result );
	OutputDebugStringA( "}\n" );
	return	result;
}
void	currency_test(){
	purchase_test( 123, 68 );
}
int	main(){
	currency_test();
	return	0;
}

準備その３：通貨型を作ってみる

毎回数値から金種に直すのは面倒なので、その情報を持っておける通貨型を書いてみましょう

const int	c_currency_denominations_jpy[] = { 1, 5, 10, 50, 100, 500, 1000, 5000, 10000 };

struct currency_t {
	int	values[elementsof( c_currency_denominations_jpy )];
	
	int	get() const {
		int	result = 0;
		for( size_t	n = 0; n < elementsof( c_currency_denominations_jpy ); ++n ){
			result += values[n] * c_currency_denominations_jpy[n];
		}
		return	result;
	}
	void	set( int	currency_value ){
		for( size_t	n = 0; n < elementsof( c_currency_denominations_jpy ); ++n ){
			size_t	m = elementsof( c_currency_denominations_jpy ) - n - 1;
			values[m] = currency_value / c_currency_denominations_jpy[m];
			currency_value %= c_currency_denominations_jpy[m];
		}
	}
	currency_t&	operator+=( const currency_t&	rhs ){
		for( size_t	n = 0; n < elementsof( values ); ++n ){
			values[n] += rhs.values[n];
		}
		return	*this;
	}
	currency_t&	operator-=( const currency_t&	rhs ){
		for( size_t	n = 0; n < elementsof( values ); ++n ){
			values[n] -= rhs.values[n];
		}
		return	*this;
	}
	currency_t	operator+( const currency_t&	rhs ){
		currency_t	result( *this );
		result += rhs;
		return	result;
	}
	currency_t	operator-( const currency_t&	rhs ){
		currency_t	result( *this );
		result -= rhs;
		return	result;
	}
	currency_t():
	values()
	{
	}
	explicit currency_t( int	currency_value ):
	values()
	{
		set( currency_value );
	}
	currency_t( const currency_t&	rhs ):
	values()
	{
		operator=( rhs );
	}
	currency_t&	operator=( const currency_t&	rhs ){
		if( this != &rhs ){
			memcpy( values, rhs.values, sizeof( values ));
		}
		return	*this;
	}
};

void	print_currency( const char*	prompt_text, const currency_t&	currency ){
	OutputDebugStringA( stringprintf( "\t%s%d円 {\n", prompt_text, currency.get()));
	for( size_t	n = 0; n < elementsof( c_currency_denominations_jpy ); ++n ){
		int	d = currency.values[n];
		OutputDebugStringA( stringprintf( "\t\t%5d円 %d枚\n", c_currency_denominations_jpy[n], d ));
	}
	OutputDebugStringA( "\t}\n" );
}
int	purchase_test( int	current_value, int	price ){
	currency_t	current( current_value );
	OutputDebugStringA( stringprintf( "%d円あるときに %d円のものを買う {\n", current_value, price ));
	print_currency( "所持金 ", current );
	currency_t	payment = current;
	print_currency( "支払い ", payment );
	currency_t	change( payment.get() - price );
	print_currency( "お釣り ", change );
	currency_t	result( current - payment + change );
	print_currency( "残り ", result );
	OutputDebugStringA( "}\n" );
	return	result.get();
}
void	currency_test(){
	purchase_test( 123, 68 );
}
int	main(){
	currency_test();
	return	0;
}

金種を考慮した計算

準備が整ったらいよいよ金種を考慮した計算をしてみましょう

普段自分がお釣りを最小にするときにどんな計算をしているかを思い出してみましょう

const int	c_currency_denominations_jpy[] = { 1, 5, 10, 50, 100, 500, 1000, 5000, 10000 };

struct currency_t {
	int	values[elementsof( c_currency_denominations_jpy )];
	
	int	get() const {
		int	result = 0;
		for( size_t	n = 0; n < elementsof( c_currency_denominations_jpy ); ++n ){
			result += values[n] * c_currency_denominations_jpy[n];
		}
		return	result;
	}
	void	set( int	currency_value ){
		for( size_t	n = 0; n < elementsof( c_currency_denominations_jpy ); ++n ){
			size_t	m = elementsof( c_currency_denominations_jpy ) - n - 1;
			values[m] = currency_value / c_currency_denominations_jpy[m];
			currency_value %= c_currency_denominations_jpy[m];
		}
	}
	currency_t&	operator+=( const currency_t&	rhs ){
		for( size_t	n = 0; n < elementsof( values ); ++n ){
			values[n] += rhs.values[n];
		}
		return	*this;
	}
	currency_t&	operator-=( const currency_t&	rhs ){
		for( size_t	n = 0; n < elementsof( values ); ++n ){
			values[n] -= rhs.values[n];
		}
		return	*this;
	}
	currency_t	operator+( const currency_t&	rhs ){
		currency_t	result( *this );
		result += rhs;
		return	result;
	}
	currency_t	operator-( const currency_t&	rhs ){
		currency_t	result( *this );
		result -= rhs;
		return	result;
	}
	currency_t	reasonable_payment( int	price_value ) const {
		if( price_value <= 0 ){
		// 只でくれるなら何も払わないよ
			return	currency_t( 0 );
		}
		else if( price_value >= get()){
		// 値段が所持金以上だったら全額出すしかないよ
			return	*this;
		}
		// 各桁について所持金が足りないなら代わりに上の桁を一枚多く出すよ
		currency_t	price( price_value );
		currency_t	result( 0 );
		for( size_t	n = 0; n < elementsof( values )-1; ++n ){
			if( price.values[n] <= values[n] ){
				result.values[n] = price.values[n];
			}
			else{
				++price.values[n+1];
			}
		}
		return	result;
	}
	currency_t():
	values()
	{
	}
	explicit currency_t( int	currency_value ):
	values()
	{
		set( currency_value );
	}
	currency_t( const currency_t&	rhs ):
	values()
	{
		operator=( rhs );
	}
	currency_t&	operator=( const currency_t&	rhs ){
		if( this != &rhs ){
			memcpy( values, rhs.values, sizeof( values ));
		}
		return	*this;
	}
};

void	print_currency( const char*	prompt_text, const currency_t&	currency ){
	OutputDebugStringA( stringprintf( "\t%s%d円 {\n", prompt_text, currency.get()));
	for( size_t	n = 0; n < elementsof( c_currency_denominations_jpy ); ++n ){
		int	d = currency.values[n];
		OutputDebugStringA( stringprintf( "\t\t%5d円 %d枚\n", c_currency_denominations_jpy[n], d ));
	}
	OutputDebugStringA( "\t}\n" );
}
int	purchase_test( int	current_value, int	price ){
	currency_t	current( current_value );
	OutputDebugStringA( stringprintf( "%d円あるときに %d円のものを買う {\n", current_value, price ));
	print_currency( "所持金 ", current );
	currency_t	payment = current.reasonable_payment( price );
	print_currency( "支払い ", payment );
	currency_t	change( payment.get() - price );
	print_currency( "お釣り ", change );
	currency_t	result( current - payment + change );
	print_currency( "残り ", result );
	OutputDebugStringA( "}\n" );
	return	result.get();
}
void	currency_test(){
	purchase_test( 123, 68 );
}
int	main(){
	currency_test();
	return	0;
}

日本円だけじゃなくて他の通貨も使えるようにしてみる

ここまではずっと日本円の金種を前提にしていましたが、世の中にある通貨は日本円だけではありません
他の通貨も使えるようにしてみましょう

struct currency_traits {
	struct jpy {
		template<typename _value_type> struct denominations {
			typedef _value_type	value_type;
			static const size_t	length = 9;
			static const value_type	values[length];
			static const value_type	minor_denomination = 0;
		};
	};
	struct usd {
		template<typename _value_type> struct denominations {
			typedef _value_type	value_type;
			static const size_t	length = 12;
			static const value_type	values[length];
			static const value_type	minor_denomination = 100;
		};
	};
	template<typename traits_type> static typename traits_type::value_type	major_denomination( typename traits_type::value_type	value ){
		return	detail::major_denomination_helper_t<traits_type>::major_denomination( value );
	}
	template<typename traits_type> static typename traits_type::value_type	minor_denomination( typename traits_type::value_type	value ){
		return	detail::minor_denomination_helper_t<traits_type>::minor_denomination( value );
	}
	template<typename traits_type> static typename traits_type::value_type	is_minor_denomination( typename traits_type::value_type	value ){
		return	!!detail::minor_denomination_helper_t<traits_type>::minor_denomination( value );
	}
private:
	struct detail {
		template<typename traits_type,bool = less_than_or_equal_to_t<traits_type::minor_denomination,0>::value> struct major_denomination_helper_t {
			static typename traits_type::value_type	major_denomination( typename traits_type::value_type	value ){
				return	value;
			}
		};
		template<typename traits_type> struct major_denomination_helper_t<traits_type,false> {
			static typename traits_type::value_type	major_denomination( typename traits_type::value_type	value ){
				return	value / traits_type::minor_denomination;
			}
		};
		template<typename traits_type,bool = less_than_or_equal_to_t<traits_type::minor_denomination,0>::value> struct minor_denomination_helper_t {
			static typename traits_type::value_type	minor_denomination( typename traits_type::value_type ){
				return	0;
			}
		};
		template<typename traits_type> struct minor_denomination_helper_t<traits_type,false> {
			static typename traits_type::value_type	minor_denomination( typename traits_type::value_type	value ){
				return	value % traits_type::minor_denomination;
			}
		};
	};
};
template<typename _value_type> const _value_type	currency_traits::jpy::denominations<_value_type>::values[] = { 1, 5, 10, 50, 100, 500, 1000, 5000, 10000 };
template<typename _value_type> const _value_type	currency_traits::usd::denominations<_value_type>::values[] = { 1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };

// value_type は signed がいいよ。今のところ unsigned は気にしない
template<typename traits_type> struct currency_t : public traits_type {
	typename traits_type::value_type	values[traits_type::length];
	
	typename traits_type::value_type	get_count() const {
		typename traits_type::value_type	result = 0;
		for( size_t	n = 0; n < traits_type::length; ++n ){
			result += values[n];
		}
		return	result;
	}
	typename traits_type::value_type	get() const {
		typename traits_type::value_type	result = 0;
		for( size_t	n = 0; n < traits_type::length; ++n ){
			result += values[n] * traits_type::values[n];
		}
		return	result;
	}
	currency_t&	set( typename traits_type::value_type	currency ){
		// 枚数を気にしないときは各桁が最小枚数の状態とするよ
		// （例えば500円なら100円5枚とか10円50枚とかにするんじゃなくて500円玉1枚にするよ）
		size_t	n = traits_type::length;
		while( --n > 0 ){
			values[n] = currency / traits_type::values[n];
			currency %= traits_type::values[n];
		}
		values[0] = currency;
		return	*this;
	}
	currency_t&	add( const currency_t&	rhs ){
		for( size_t	n = 0; n < traits_type::length; ++n ){
			values[n] += rhs.values[n];
		}
		return	*this;
	}
	currency_t&	sub( const currency_t&	rhs ){
		for( size_t	n = 0; n < traits_type::length; ++n ){
			values[n] -= rhs.values[n];
		}
		return	*this;
	}
	currency_t	reasonable_payment( typename traits_type::value_type	price_value ) const {
		if( price_value <= 0 ){
		// 只でくれるなら何も払わないよ
			return	currency_t( 0 );
		}
		else if( price_value >= get()){
		// 値段が所持金以上だったら全額出すしかないよ
			return	*this;
		}
		// 各桁について所持金が足りないなら代わりに上の桁を一枚多く出すよ
		currency_t	price( price_value );
		currency_t	result( 0 );
		for( size_t	n = 0; n < traits_type::length-1; ++n ){
			if( price.values[n] <= values[n] ){
				result.values[n] = price.values[n];
			}
			else{
				++price.values[n+1];
			}
		}
		return	result;
	}
	currency_t&	optimize(){
		// 各桁の枚数を最小化するよ
		// （例えば100円5枚とか10円50枚とかはまとめて500円玉1枚にするよ）
		typename traits_type::value_type	m = 0;
		for( size_t	n = 0; n < traits_type::length-1; ++n ){
			if( values[n] < 0 ){
				typename traits_type::value_type	i = 1;
				while(( traits_type::values[n+1] * i ) % traits_type::values[n] ){
					++i;
				}
				values[n+1] -= i;
				values[n] += ( traits_type::values[n+1] * i ) / traits_type::values[n];
			}
			typename traits_type::value_type	value = values[n] + m;
			typename traits_type::value_type	s = 1;
			if( value < 0 ){
				s *= -1;
				value *= -1;
			}
			values[n] = s * ( value % traits_type::values[n+1] );
			m = s * ( value / traits_type::values[n+1] );
		}
		values[traits_type::length-1] += m;
		return	*this;
	}
	
	currency_t():
	values()
	{
	}
	explicit currency_t( typename traits_type::value_type	currency ):
	values()
	{
		set( currency );
	}
	currency_t( const currency_t&	rhs ):
	values()
	{
		operator=( rhs );
	}
	currency_t&	operator=( const currency_t&	rhs ){
		if( this != &rhs ){
			memcpy( values, rhs.values, sizeof( values ));
		}
		return	*this;
	}
	currency_t&	operator+=( const currency_t&	rhs ){
		return	add( rhs );
	}
	currency_t&	operator-=( const currency_t&	rhs ){
		return	sub( rhs );
	}
	bool	operator<( const currency_t&	rhs ) const {
		bool	result = true;
		for( size_t	n = 0; n < traits_type::length; ++n ){
			if( values[n] < rhs.values[n] ){
				result = false;
				break;
			}
		}
		return	result;
	}
	currency_t	operator-() const {
		currency_t	result( *this );
		for( size_t	n = 0; n < traits_type::length; ++n ){
			result.values[n] *= -1;
		}
		return	result;
	}
	currency_t	operator+( const currency_t&	rhs ) const {
		currency_t	result( *this );
		return	result.operator+=( rhs );
	}
	currency_t	operator-( const currency_t&	rhs ) const {
		currency_t	result( *this );
		return	result.operator-=( rhs );
	}
};

template<typename traits_type> struct currency_string_t {
	static std::string	to_string( typename traits_type::value_type );
};
template<typename _value_type> struct currency_string_t<currency_traits::jpy::denominations<_value_type> > {
	static std::string	to_string( _value_type	value ){
		return	stringprintf( "%d円", value );
	}
};
template<typename _value_type> struct currency_string_t<currency_traits::usd::denominations<_value_type> > {
	static std::string	to_string( _value_type	value ){
		_value_type	major = currency_traits::major_denomination<currency_traits::usd::denominations<_value_type> >( value );
		_value_type	minor = currency_traits::minor_denomination<currency_traits::usd::denominations<_value_type> >( value );
		if( major && minor ){
			return	stringprintf( "%dドル %dセント", major, minor );
		}
		else if( major ){
			return	stringprintf( "%dドル", major );
		}
		else{
			return	stringprintf( "%dセント", minor );
		}
	}
};
template<typename traits_type> struct currency_denomination_string_t {
	static std::string	to_string( typename traits_type::value_type );
};
template<typename _value_type> struct currency_denomination_string_t<currency_traits::jpy::denominations<_value_type> > {
	static std::string	to_string( _value_type	denomination ){
		return	stringprintf( "%5d円", denomination );
	}
};
template<typename _value_type> struct currency_denomination_string_t<currency_traits::usd::denominations<_value_type> > {
	static std::string	to_string( _value_type	denomination ){
		if( currency_traits::is_minor_denomination<currency_traits::usd::denominations<_value_type> >( denomination )){
			return	stringprintf( "%3dセント", denomination );
		}
		else{
			return	stringprintf( "%3dドル  ", currency_traits::major_denomination<currency_traits::usd::denominations<_value_type> >( denomination ));
		}
	}
};

template<typename traits_type> inline void	print_currency( const std::string&	prompt_text, const currency_t<traits_type>&	currency ){
	OutputDebugStringA( "\t" + prompt_text + currency_string_t<traits_type>::to_string(currency.get()) + " {\n");
	for( size_t	n = 0; n < traits_type::length; ++n ){
		OutputDebugStringA( "\t\t" + currency_denomination_string_t<traits_type>::to_string( traits_type::values[n] ) + stringprintf( " %d枚\n", currency.values[n] ));
	}
	OutputDebugStringA( "\t}\n");
}
template<typename traits_type> inline int	purchase_test( const currency_t<traits_type>&	current, typename traits_type::value_type	price ){
	OutputDebugStringA( currency_string_t<traits_type>::to_string( current.get()) + "あるときに " + currency_string_t<traits_type>::to_string( price ) + "のものを買う {\n");
	print_currency( "所持金 ", current );
	currency_t<traits_type>	payment = current.reasonable_payment( price );
	OutputDebugStringA( "\t" + currency_string_t<traits_type>::to_string( price ) + "に " + currency_string_t<traits_type>::to_string( payment.get()) + "払う\n");
	print_currency( "支払い ", payment );
	currency_t<traits_type>	change( payment.get() - price );
	print_currency( "お釣り ", change );
	currency_t<traits_type>	result( current - payment + change );
	print_currency( "残り ", result );
	OutputDebugStringA( "}\n");
	return	result.get();
}
template<typename traits_type> inline typename traits_type::value_type	purchase_test( typename traits_type::value_type	current, typename traits_type::value_type	price ){
	return	purchase_test( currency_t<traits_type>( current ), price );
}
template<typename value_type> inline value_type	purchase_test( value_type	current, value_type	price ){
	return	purchase_test<currency_traits::jpy::denominations<value_type> >( current, price );
}
void	currency_test(){
	purchase_test( 123, 68 );
}
int	main(){
	currency_test();
	return	0;
}

コンパイル時に金種を取得できるようにしてみる

namespace currency_traits {
namespace jpy {
namespace detail {
template<int> struct denomination_order;
template<> struct denomination_order<1> { static const size_t	value = 0; };
template<> struct denomination_order<5> { static const size_t	value = 1; };
template<> struct denomination_order<10> { static const size_t	value = 2; };
template<> struct denomination_order<50> { static const size_t	value = 3; };
template<> struct denomination_order<100> { static const size_t	value = 4; };
template<> struct denomination_order<500> { static const size_t	value = 5; };
template<> struct denomination_order<1000> { static const size_t	value = 6; };
template<> struct denomination_order<5000> { static const size_t	value = 7; };
template<> struct denomination_order<10000> { static const size_t	value = 8; };
template<typename value_type, size_t order> struct denomination {
	static const value_type	value = 0;
};
template<typename value_type> struct denomination<value_type,denomination_order<1>::value> { static const value_type	value = 1; };
template<typename value_type> struct denomination<value_type,denomination_order<5>::value> { static const value_type	value = 5; };
template<typename value_type> struct denomination<value_type,denomination_order<10>::value> { static const value_type	value = 10; };
template<typename value_type> struct denomination<value_type,denomination_order<50>::value> { static const value_type	value = 50; };
template<typename value_type> struct denomination<value_type,denomination_order<100>::value> { static const value_type	value = 100; };
template<typename value_type> struct denomination<value_type,denomination_order<500>::value> { static const value_type	value = 500; };
template<typename value_type> struct denomination<value_type,denomination_order<1000>::value> { static const value_type	value = 1000; };
template<typename value_type> struct denomination<value_type,denomination_order<5000>::value> { static const value_type	value = 5000; };
template<typename value_type> struct denomination<value_type,denomination_order<10000>::value> { static const value_type	value = 10000; };
template<typename value_type, size_t n = 0, bool = !denomination<value_type,n>::value> struct length_helper_t {
	static const size_t	value = n;
};
template<typename value_type,size_t n> struct length_helper_t<value_type,n,false> {
	static const size_t	value = length_helper_t<value_type,n+1>::value;
};
}
template<typename _value_type> struct denominations {
	typedef _value_type	value_type;
	static const size_t	length = detail::length_helper_t<value_type>::value;
	static const _value_type	values[length];
	static const _value_type	minor_denomination = 0;
};
template<typename _value_type> const _value_type	denominations<_value_type>::values[] = {
	detail::denomination<_value_type,0>::value,
	detail::denomination<_value_type,1>::value,
	detail::denomination<_value_type,2>::value,
	detail::denomination<_value_type,3>::value,
	detail::denomination<_value_type,4>::value,
	detail::denomination<_value_type,5>::value,
	detail::denomination<_value_type,6>::value,
	detail::denomination<_value_type,7>::value,
	detail::denomination<_value_type,8>::value,
};
}
namespace usd {
namespace detail {
template<int> struct denomination_order;
template<> struct denomination_order<1> { static const size_t	value = 0; };
template<> struct denomination_order<5> { static const size_t	value = 1; };
template<> struct denomination_order<10> { static const size_t	value = 2; };
template<> struct denomination_order<25> { static const size_t	value = 3; };
template<> struct denomination_order<50> { static const size_t	value = 4; };
template<> struct denomination_order<100> { static const size_t	value = 5; };
template<> struct denomination_order<200> { static const size_t	value = 6; };
template<> struct denomination_order<500> { static const size_t	value = 7; };
template<> struct denomination_order<1000> { static const size_t	value = 8; };
template<> struct denomination_order<2000> { static const size_t	value = 9; };
template<> struct denomination_order<5000> { static const size_t	value = 10; };
template<> struct denomination_order<10000> { static const size_t	value = 11; };
template<typename value_type, size_t order> struct denomination {
	static const value_type	value = 0;
};
template<typename value_type> struct denomination<value_type,denomination_order<1>::value> { static const value_type	value = 1; };
template<typename value_type> struct denomination<value_type,denomination_order<5>::value> { static const value_type	value = 5; };
template<typename value_type> struct denomination<value_type,denomination_order<10>::value> { static const value_type	value = 10; };
template<typename value_type> struct denomination<value_type,denomination_order<25>::value> { static const value_type	value = 25; };
template<typename value_type> struct denomination<value_type,denomination_order<50>::value> { static const value_type	value = 50; };
template<typename value_type> struct denomination<value_type,denomination_order<100>::value> { static const value_type	value = 100; };
template<typename value_type> struct denomination<value_type,denomination_order<200>::value> { static const value_type	value = 200; };
template<typename value_type> struct denomination<value_type,denomination_order<500>::value> { static const value_type	value = 500; };
template<typename value_type> struct denomination<value_type,denomination_order<1000>::value> { static const value_type	value = 1000; };
template<typename value_type> struct denomination<value_type,denomination_order<2000>::value> { static const value_type	value = 2000; };
template<typename value_type> struct denomination<value_type,denomination_order<5000>::value> { static const value_type	value = 5000; };
template<typename value_type> struct denomination<value_type,denomination_order<10000>::value> { static const value_type	value = 10000; };
template<typename value_type, size_t n = 0, bool = !denomination<value_type,n>::value> struct length_helper_t {
	static const size_t	value = n;
};
template<typename value_type, size_t n> struct length_helper_t<value_type,n,false> {
	static const size_t	value = length_helper_t<value_type,n+1>::value;
};
}
template<typename _value_type> struct denominations {
	typedef _value_type	value_type;
	static const size_t	length = detail::length_helper_t<_value_type>::value;
	static const _value_type	values[length];
	static const _value_type	minor_denomination = 100;
};
template<typename _value_type> const _value_type	denominations<_value_type>::values[] = {
	detail::denomination<_value_type,0>::value,
	detail::denomination<_value_type,1>::value,
	detail::denomination<_value_type,2>::value,
	detail::denomination<_value_type,3>::value,
	detail::denomination<_value_type,4>::value,
	detail::denomination<_value_type,5>::value,
	detail::denomination<_value_type,6>::value,
	detail::denomination<_value_type,7>::value,
	detail::denomination<_value_type,8>::value,
	detail::denomination<_value_type,9>::value,
	detail::denomination<_value_type,10>::value,
	detail::denomination<_value_type,11>::value,
};
}
namespace detail {
template<typename traits_type,bool = less_than_or_equal_to_t<traits_type::minor_denomination,0>::value> struct major_denomination_helper_t {
	static typename traits_type::value_type	major_denomination( typename traits_type::value_type	value ){
		return	value;
	}
};
template<typename traits_type> struct major_denomination_helper_t<traits_type,false> {
	static typename traits_type::value_type	major_denomination( typename traits_type::value_type	value ){
		return	value / traits_type::minor_denomination;
	}
};
template<typename traits_type,bool = less_than_or_equal_to_t<traits_type::minor_denomination,0>::value> struct minor_denomination_helper_t {
	static typename traits_type::value_type	minor_denomination( typename traits_type::value_type ){
		return	0;
	}
};
template<typename traits_type> struct minor_denomination_helper_t<traits_type,false> {
	static typename traits_type::value_type	minor_denomination( typename traits_type::value_type	value ){
		return	value % traits_type::minor_denomination;
	}
};
}
template<typename traits_type> static typename traits_type::value_type	major_denomination( typename traits_type::value_type	value ){
	return	detail::major_denomination_helper_t<traits_type>::major_denomination( value );
}
template<typename traits_type> static typename traits_type::value_type	minor_denomination( typename traits_type::value_type	value ){
	return	detail::minor_denomination_helper_t<traits_type>::minor_denomination( value );
}
template<typename traits_type> static typename traits_type::value_type	is_minor_denomination( typename traits_type::value_type	value ){
	return	!!detail::minor_denomination_helper_t<traits_type>::minor_denomination( value );
}
}

// value_type は signed がいいよ。今のところ unsigned は気にしない
template<typename traits_type> struct currency_t : public traits_type {
	typename traits_type::value_type	values[traits_type::length];
	
	typename traits_type::value_type	get_count() const {
		typename traits_type::value_type	result = 0;
		for( size_t	n = 0; n < traits_type::length; ++n ){
			result += values[n];
		}
		return	result;
	}
	typename traits_type::value_type	get() const {
		typename traits_type::value_type	result = 0;
		for( size_t	n = 0; n < traits_type::length; ++n ){
			result += values[n] * traits_type::values[n];
		}
		return	result;
	}
	currency_t&	set( typename traits_type::value_type	currency ){
		// 枚数を気にしないときは各桁が最小枚数の状態とするよ
		// （例えば500円なら100円5枚とか10円50枚とかにするんじゃなくて500円玉1枚にするよ）
		size_t	n = traits_type::length;
		while( --n > 0 ){
			values[n] = currency / traits_type::values[n];
			currency %= traits_type::values[n];
		}
		values[0] = currency;
		return	*this;
	}
	currency_t&	add( const currency_t&	rhs ){
		for( size_t	n = 0; n < traits_type::length; ++n ){
			values[n] += rhs.values[n];
		}
		return	*this;
	}
	currency_t&	sub( const currency_t&	rhs ){
		for( size_t	n = 0; n < traits_type::length; ++n ){
			values[n] -= rhs.values[n];
		}
		return	*this;
	}
	currency_t	reasonable_payment( typename traits_type::value_type	price_value ) const {
		if( price_value <= 0 ){
		// 只でくれるなら何も払わないよ
			return	currency_t( 0 );
		}
		else if( price_value >= get()){
		// 値段が所持金以上だったら全額出すしかないよ
			return	*this;
		}
		// 各桁について所持金が足りないなら代わりに上の桁を一枚多く出すよ
		currency_t	price( price_value );
		currency_t	result( 0 );
		for( size_t	n = 0; n < traits_type::length-1; ++n ){
			if( price.values[n] <= values[n] ){
				result.values[n] = price.values[n];
			}
			else{
				++price.values[n+1];
			}
		}
		return	result;
	}
	currency_t&	optimize(){
		// 各桁の枚数を最小化するよ
		// （例えば100円5枚とか10円50枚とかはまとめて500円玉1枚にするよ）
		typename traits_type::value_type	m = 0;
		for( size_t	n = 0; n < traits_type::length-1; ++n ){
			if( values[n] < 0 ){
				typename traits_type::value_type	i = 1;
				while(( traits_type::values[n+1] * i ) % traits_type::values[n] ){
					++i;
				}
				values[n+1] -= i;
				values[n] += ( traits_type::values[n+1] * i ) / traits_type::values[n];
			}
			typename traits_type::value_type	value = values[n] + m;
			typename traits_type::value_type	s = 1;
			if( value < 0 ){
				s *= -1;
				value *= -1;
			}
			values[n] = s * ( value % traits_type::values[n+1] );
			m = s * ( value / traits_type::values[n+1] );
		}
		values[traits_type::length-1] += m;
		return	*this;
	}
	
	currency_t():
	values()
	{
	}
	explicit currency_t( typename traits_type::value_type	currency ):
	values()
	{
		set( currency );
	}
	currency_t( const currency_t&	rhs ):
	values()
	{
		operator=( rhs );
	}
	currency_t&	operator=( const currency_t&	rhs ){
		if( this != &rhs ){
			memcpy( values, rhs.values, sizeof( values ));
		}
		return	*this;
	}
	currency_t&	operator+=( const currency_t&	rhs ){
		return	add( rhs );
	}
	currency_t&	operator-=( const currency_t&	rhs ){
		return	sub( rhs );
	}
	bool	operator<( const currency_t&	rhs ) const {
		bool	result = true;
		for( size_t	n = 0; n < traits_type::length; ++n ){
			if( values[n] < rhs.values[n] ){
				result = false;
				break;
			}
		}
		return	result;
	}
	currency_t	operator-() const {
		currency_t	result( *this );
		for( size_t	n = 0; n < traits_type::length; ++n ){
			result.values[n] *= -1;
		}
		return	result;
	}
	currency_t	operator+( const currency_t&	rhs ) const {
		currency_t	result( *this );
		return	result.operator+=( rhs );
	}
	currency_t	operator-( const currency_t&	rhs ) const {
		currency_t	result( *this );
		return	result.operator-=( rhs );
	}
};

template<typename traits_type> struct currency_string_t {
	static std::string	to_string( typename traits_type::value_type );
};
template<typename _value_type> struct currency_string_t<currency_traits::jpy::denominations<_value_type> > {
	static std::string	to_string( _value_type	value ){
		return	stringprintf( "%d円", value );
	}
};
template<typename _value_type> struct currency_string_t<currency_traits::usd::denominations<_value_type> > {
	static std::string	to_string( _value_type	value ){
		_value_type	major = currency_traits::major_denomination<currency_traits::usd::denominations<_value_type> >( value );
		_value_type	minor = currency_traits::minor_denomination<currency_traits::usd::denominations<_value_type> >( value );
		if( major && minor ){
			return	stringprintf( "%dドル %dセント", major, minor );
		}
		else if( major ){
			return	stringprintf( "%dドル", major );
		}
		else{
			return	stringprintf( "%dセント", minor );
		}
	}
};
template<typename traits_type> struct currency_denomination_string_t {
	static std::string	to_string( typename traits_type::value_type );
};
template<typename _value_type> struct currency_denomination_string_t<currency_traits::jpy::denominations<_value_type> > {
	static std::string	to_string( _value_type	denomination ){
		return	stringprintf( "%5d円", denomination );
	}
};
template<typename _value_type> struct currency_denomination_string_t<currency_traits::usd::denominations<_value_type> > {
	static std::string	to_string( _value_type	denomination ){
		if( currency_traits::is_minor_denomination<currency_traits::usd::denominations<_value_type> >( denomination )){
			return	stringprintf( "%3dセント", denomination );
		}
		else{
			return	stringprintf( "%3dドル  ", currency_traits::major_denomination<currency_traits::usd::denominations<_value_type> >( denomination ));
		}
	}
};

template<typename traits_type> inline void	print_currency( const std::string&	prompt_text, const currency_t<traits_type>&	currency ){
	OutputDebugStringA( "\t" + prompt_text + currency_string_t<traits_type>::to_string(currency.get()) + " {\n");
	for( size_t	n = 0; n < traits_type::length; ++n ){
		OutputDebugStringA( "\t\t" + currency_denomination_string_t<traits_type>::to_string( traits_type::values[n] ) + stringprintf( " %d枚\n", currency.values[n] ));
	}
	OutputDebugStringA( "\t}\n");
}
template<typename traits_type> inline int	purchase_test( const currency_t<traits_type>&	current, typename traits_type::value_type	price ){
	OutputDebugStringA( currency_string_t<traits_type>::to_string( current.get()) + "あるときに " + currency_string_t<traits_type>::to_string( price ) + "のものを買う {\n");
	print_currency( "所持金 ", current );
	currency_t<traits_type>	payment = current.reasonable_payment( price );
	OutputDebugStringA( "\t" + currency_string_t<traits_type>::to_string( price ) + "に " + currency_string_t<traits_type>::to_string( payment.get()) + "払う\n");
	print_currency( "支払い ", payment );
	currency_t<traits_type>	change( payment.get() - price );
	print_currency( "お釣り ", change );
	currency_t<traits_type>	result( current - payment + change );
	print_currency( "残り ", result );
	OutputDebugStringA( "}\n");
	return	result.get();
}
template<typename traits_type> inline typename traits_type::value_type	purchase_test( typename traits_type::value_type	current, typename traits_type::value_type	price ){
	return	purchase_test( currency_t<traits_type>( current ), price );
}
template<typename value_type> inline value_type	purchase_test( value_type	current, value_type	price ){
	return	purchase_test<currency_traits::jpy::denominations<value_type> >( current, price );
}
void	currency_test(){
	purchase_test( 123, 68 );
}
int	main(){
	currency_test();
	return	0;
}

前提条件のない場合

ここまでは各桁の枚数は上の桁よりも大きくならないという前提がありましたね
2345円と言えば 1000円札を 2枚、100円玉を 3枚、10円玉を 4枚、5円玉を 1枚 と決まっていました

しかし現実を考えてみると、どれが何枚あっても構いませんよね

今までのコードは前提条件が崩れると正しく機能しません
前提条件のない自由な枚数を扱えるようにしてみましょう