id:ukiya:20070603 で書いたワリカンのアプリですが、
アルゴリズムは自分で適当に考えたものです。
- 大中小の比率に応じて合計金額を分ける
- 単位金額（１００円とか）で切り捨て
- 切り捨てた分を、大、中、小のどこかに乗せられれば乗せる
- 例えば、切り捨てた分が1000円で、大が10人以下なら、大の人が100円アップ
- 切り捨てた分が500円で、大が6人居たら、乗せられないので中→小と乗せられるか試す
- ただしこの計算の結果、大＞中＞小 の金額の順序が狂う場合は乗せない
- どこにも乗せられなくなるまで繰り返す
- 「多め」に集める場合は、それでも残った端数は、大→中→小の順で人の居る所に乗せる
- 例えば端数が100円で、大が10人いたら、大に+100円すると900円余る
- この余ったものは、小→中 の順で還付できれば還付する。
- 例えば端数処理の結果900円取りすぎて、小が9人居れば100円ずつ返す
色々アルゴリズムを考えてみると面白いかもしれませんが、
すでに数学的に最適なものがあるのかもしれません。
要するに差額と与えられた比率からの乖離の最小値を求める計算ですので、
漸近法で連立方程式を解けば最適解が得られるのかも。
今度暇になったらちょっと考えてみよう。
