supercon

問題に目を通した。感想ぽいもの。
kやらに聞いた時はナップサック系かと思ったが、どうだろう。微妙だ。去年(巡回セールスマン問題)や一昨年(反復パターンの探索)の問題のほうが好きだ。

問1

日本の貨幣制度はまともに造られているので、普通に額面の大きい方からみていけばいいと思う。ところで、20枚縛りは無いのだろうか*1。

問2

複数回答可能だから、問1同様、上から見ていって一応解を出したあと最適化すればいいと思う。額面の大きい奴から崩してゆくとか。

問3

釣り銭システムで一気に複雑化したような気もするが、問2と同じ感じでいいのかもしれない。いや、崩し方のバリエーションが増えたからしんどいか。
まぁ、がんばって。

*1:同種の貨幣は同時に21枚以上使えない(店側が拒否できる)ことになっている