※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。




Problem 31 「硬貨の和」 †
イギリスでは硬貨はポンド£とペンスpがあり,一般的に流通している硬貨は以下の8種類である.

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

以下の方法で£2を作ることが可能である.

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

これらの硬貨を使って£2を作る方法は何通りあるか?





解法
初めてこの問題にPrologで挑戦した時は破壊的代入も配列もstd::mapもないPrologでどうやって動的計画法をするか悩みました。
基本がわかれば考え方は簡単。
1ペンスで作れる組み合わせを全部計算し、[金額、組み合わせ数]を基本に
[0,1],[1,1][2,1],,[200,1]
と集合を作ります。

この集合に今度は2ペンスを0~200個まで足した場合の集合で金額が200までになるものだけを取り出して新しく集合を作ります。
この集合をソートして同じ金額のものを集計していけば1と2を使った組み合わせが出ます。
以下これの繰り返しです。


calc(Vs,Coin,[NV,Count]):-
	member([V,Count],Vs),
	between(0,200,C),
	NV is V+C*Coin,
	(NV=<200).

union_sum([],V,[V]):-!.
union_sum([[V,Count1]|Vs],[V,Count2],Result):-
	!,
	Count3 is Count1+Count2,
	union_sum(Vs,[V,Count3],Result).

union_sum([V|Vs],V1,[V1|Result]):-
	union_sum(Vs,V,Result).

next_calc([],Vs,Ans):-
 	!,
	member([200,Ans],Vs).

next_calc([Coin|Coins],Vs,Ans):-
	findall(NV,calc(Vs,Coin,NV),NVs),
 	msort(NVs,NVs1),
[Top|NVs2]=NVs1,
 	union_sum(NVs2,Top,NVs3),
	next_calc(Coins,NVs3,Ans).
main31:-
	next_calc([1,2,5,10,20,50,100,200],[[0,1]],Ans),
	write(Ans).