切手の組み合わせの計算
払いたい金額を入れると、日本郵便の普通切手(1円〜500円)だけを使って、ちょうどその金額になる、いちばん枚数が少ない組み合わせを計算します。
計算方法
金額を1円ずつ増やしながら、そこまでに必要な最少の枚数を、1つ小さい金額までの最少の枚数から順に計算していく方法(動的計画法)で、ぴったり作れる組み合わせのうち枚数が最少のものを求めています。
例:56円を作るとき、50円+5円+1円の3枚より、40円+16円の2枚のほうが少ない枚数で作れるため、こちらが選ばれます。
使う額面は、日本郵便が現在売っている普通切手(1円・2円・5円・10円・16円・20円・22円・26円・30円・40円・50円・85円・100円・110円・120円・140円・180円・270円・300円・350円・500円の21種類)です。
考え方を説明します。小さい金額から順に、その金額をぴったり作るのに必要な最少の枚数を記録していきます。ある金額を作るには、そこから切手1枚分を引いた金額の最少枚数に1を足せばよいので、全部の額面を試していちばん少ないものを選びます。これをくり返すと、目的の金額での最少枚数が決まります。
例:1,830円なら、500円3枚・300円1枚・30円1枚の合計5枚です。1,220円なら、500円2枚・180円1枚・40円1枚の4枚になります。
気をつけること。日本郵便が売っている普通切手21種類(1円から500円)だけを使っています。記念切手やグリーティング切手の額面は入っていません。同じ枚数になる組み合わせが複数あるときは、そのうちの1つを表示します。窓口に出す前に、切手を貼る面が足りるかどうかも確かめてください。
よくある質問
なぜ大きい額面から順に選ばないの?
大きい額面から順に選ぶ(両替のような)方法だと、かえって枚数が多くなることがあるためです。このツールは、すべての組み合わせの中から枚数が最少になるものを計算しています。
慶弔用の切手も使える?
慶弔用切手(弔事用85円・慶事用85円・110円など)は、絵柄が違うだけで額面は普通切手と同じです。組み合わせの中では、同じ額面の普通切手として数えられます。
1円に満たない端数があるときは?
このツールは1円単位の金額だけを計算します。端数がある場合は、切り上げるか切り下げるかを先に決めて、1円単位の金額にしてから入れてください。
金額を0円にするとどうなる?
計算できません。1円以上の整数で入れてください。