簡易書留とChange-Making Problem - 牧場生まれの牛乳

この前、知り合いと一緒に、入学願書の返信用封筒に貼る切手を買いに行った。返信は簡易書留で郵送されるので、414円分の切手を買う必要があった。普通は、94円（通常の配達料金）+ 320円（簡易書留用の追加料金）で切手を買うのだが、コンビニには、1円, 10円, 63円, 84円, 140円の5種類の切手のみが販売されていた。

知り合いはちょうど414円になる切手の組み合わせを考えた。貪欲法で計算を行うと、140円切手2枚 + 84円切手1枚 + 10円切手5枚, 合計8枚の切手を買えばちょうど414円になるので、8枚切手を購入することにした。コンビニからの帰り道、僕らは「この問題、AtCoderでたまに見る『支払う枚数を最小にする問題』じゃん」という話をしながら帰っていた。

実際、今年の7月に行われたABC208でも同様の問題が出ている。

atcoder.jp

さて、今回は8枚切手を購入したが、果たしてこれは最良の購入方法なのだろうか？

今回の場合、それぞれの切手が十分にある場合、ちょうど414円になるような切手の組み合わせは538通りあり、枚数最小の組み合わせは140円切手1枚 + 84円切手1枚 + 63円切手3枚 + 1円切手1枚, 合計6枚になる。

この例からも分かる通り、一般に、貪欲法で得られた切手の組み合わせは枚数最小の組み合わせにはならない。

では、枚数が最小になるような組み合わせを求めるにはどのようにしたら良いだろうか？

動的計画法を用いれば、枚数最小の組み合わせを求めることができることが知られている。この問題は、コイン問題やChange-Making Problemとして知られている。そのため、詳しい実装方法については、もっと詳しく解説している記事を参照していただきたい。

o-treetree.hatenablog.com

だが、動的計画法は貪欲法に比べて計算量もメモリ使用量が大きく、できるならば貪欲法で計算したいだろう。特に、人間の場合、頭にDPテーブルを構築できるくらい容量がある人間を除いて、基本的には貪欲法でなければ計算ができないだろう。

今回の切手の例では、貪欲法で求めた解が枚数最小の組み合わせにならない例が存在していたが、日本の通貨体系は貪欲法で求めた解は必ず枚数最小の組み合わせになる。では、どのような場合に、貪欲法で求めた解が枚数最小の組み合わせになるのだろうか？ここからは、この条件について考えていく。

貪欲法と枚数最小の組み合わせの関係

貪欲法が枚数最小の組み合わせを生む条件は知られており、この証明*1に沿って説明をしていく。まずはじめに、これ以降の証明で利用する用語を定義する。

用語

通貨体系

$C = (c_1, c_2, \cdots, c_n) \in \mathbb{N}^n \ (c_1 > c_2 > \cdots > c_n = 1)$ を通貨体系と呼ぶ。これは、コインの種類に相当する。日本の通貨体系であれば、 $C = (10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1)$ となる。

通貨体系上での表現

$V = (v_1, v_2, \cdots, v_n) \in \mathbb{N}^n$ が、 $C \cdot V = x$ となるとき、通貨体系 $C$ での $x$ の表現と呼ぶ。文脈から明らかな場合は「通貨体系 $C$ での」という部分は省略する。これは、 $x$ 円を支払う時のコインの組み合わせに相当する。

表現 $V$ の大きさを $|V| = \sum_{i=1}^n v_i$ で定義する。これは、コインの枚数に相当する。

また、表現は、ベクトルの辞書順を用いて順序付けすることができる。つまり、ある $i\ (1 \le i \le n)$ について、 $u_i \le v_i \land \forall_{j: 1 \le j \lt i}\ u_j = v_j$ を満たすとき、 $U \le V$ と定義する。

greedy

表現 $V$ が貪欲法を用いて得られる表現である時、表現 $V$ はgreedyであるという。また、ある自然数 $x$ のgreedyな表現を $G(x)$ と表す。貪欲法では、大きい金額の硬貨から順番に使用していくため、 $x$ の表現のうち最大の表現がgreedyな表現になる。

また、自然数 $x, y$ について、 $x \lt y$ と $G(x) \lt G(y)$ は同値である。

minimal

$x$ の表現 $V$ が、大きさが最小な表現の中で最大な表現である時、表現 $V$ はminimalであるという。また、ある自然数 $x$ のminimalな表現を $M(x)$ と表す。定義より、 $M(x) \le G(x)$ である。

canonical

任意の自然数 $x$ について、 $M(x) = G(x)$ となるとき、この通貨体系はcanonicalであるという。つまり、今回求めたいことは「ある通貨体系がcanonicalであるかを判定する条件」と言い換えられる。

補題1

通貨体系 $C$ 上の表現 $U, V$ を考える。非負整数からなる $n$ 次元のベクトル $D$ が $V = U + D$ を満たしているとき、以下が成り立つ。

Vがgreedyならば、Uはgreedy
Vがminimalならば、Uはminimal

証明

（略*2）

補題2

通貨体系 $C$ を考える。また、 $w$ を $M(w) \lt G(w)$ を満たす最小の自然数とする。この時、 $M(w) \perp G(w)$ が成り立つ。

証明

背理法で証明する。 $M(w) \lt G(w)$ かつ $M(w) \perp G(w)$ でないとする。この時、 $M(w)$ の $i$ 番目の要素と $G(w)$ の $i$ 番目の要素が共に0でないような自然数 $i$ が存在する。すると、補題1より、 $M(w)$ の $i$ 番目の要素から1引いて得られる表現は、 $w - c_i$ のminimalで、 $G(w)$ の $i$ 番目の要素から1引いて得られる表現はgreedyである。また、ベクトルに定数を足しても順序関係は変化しないので、 $M(w - c_i) \lt G(w - c_i)$ となる。だが、これは $w$ の最小性に反する。

定理

通貨体系 $C$ がcanonicalでないとする。また、 $w$ を $M(w) \lt G(w)$ を満たす最小の自然数とする。また、 $i, j$ を $M(w)$ の中の0でない最初と最後の要素のインデックスとする。この時、 $M(w)$ は $G(c_{i-1} - 1)$ の $j$ 番目の要素に1足した表現である。

証明

補題2より、 $M(w) \perp G(w)$ となる。また、 $M(w) \lt G(w)$ なので、 $G(w)$ は $i$ 番目の要素よりも前の要素が1になっている必要がある。よって、 $w \gt c_{i-1}$ となる。また、補題1より、 $M(w)$ がminimalなので、 $M(w)$ の $j$ 番目の要素を1引いた表現はminimalである。また、 $w$ の最小性より、greedyでもある。よって、 $M(w - c_j) = G(w - c_j)$ である。 $G(w - c_j)$ は、 $M(w)$ と $i$ の定義より、 $i$ 番目より前の要素は全て0である。よって、 $G(w - c_j) \lt G(c_{i-1})$ 、つまり、 $w - c_j \lt c_{i-1}$ となる。よって、以下の式が得られる。

$w - c_j \lt c_{i-1} \le w$

次に、 $V = (v_1, v_2, \cdots, v_n) = G(c_{i-1} - 1)$ を考える。 $c_i \le c_{i-1} - 1 \lt c_{i-1}$ より、 $v_i \neq 0$ である。補題1より、 $G(c_{i-1} - 1)$ の $i$ 番目の要素から1引いた表現はgreedyである。よって、この表現は $G(c_{i-1} - 1 - c_i)$ である。また、 $M(w)$ の $i$ 番目の要素から1引いた表現はminimalであり、 $w$ の最小性からgreedyでもある。よって、 $G(w - c_i)$ である。先ほど得られた関係式より、 $c_{i-1} - 1 - c_i \lt w - c_i$ なので、 $G(c_{i-1} - 1 - c_i) \lt G(w - c_i)$ となる。この両辺の $i$ 番目の要素に1を加えても辞書順は変化しないので、 $V = G(c_{i-1} - 1) \lt M(w)$ となる。

また、 $M(w)$ の $j$ 番目の要素を1引いた表現はminimalであり、 $w$ の最小性からgreedyである。よって、 $G(w - c_j)$ である。 $w - c_j \le c_{i-1} - 1$ より、 $G(w - c_j) \le G(c_{i-1} - 1) = V$ である。よって、以下の式が得られる。

$G(w - c_j) \le V \lt M(w)$

$G(w - c_j)$ と $M(w)$ は $j$ 番目の要素が1異なるだけであり、 $j$ 番目以降の要素は0であるため、 $V = G(w - c_j)$ となる。よって、定理が成立する。

canonicalであることを判定するアルゴリズム

定理の対偶を取ることで、通貨体系がcanonicalであるかを調べるアルゴリズムが実装できる。これを利用してコンビニで販売されている切手がcanonicalかどうかを調べると、canonicalでなく、最小の反例 $w$ は93であることが分かる。貪欲法を用いた表現だと「84円切手1枚 + 1円切手9枚」となるが、minimalな表現は「63円切手1枚 + 10円切手3枚」である。

import numpy as np


def greedy_algorithm(C, x):
    G = np.array([0] * len(C))
    for i, ci in enumerate(C):
        G[i] = x // ci
        x = x % ci
    return G


def check_canonical(C):
    samples = []
    for i, _ in enumerate(C):
        if i == 0:
            continue

        V = greedy_algorithm(C, C[i-1] - 1)

        jmin = max([i for i, vi in enumerate(V) if vi != 0])
        for j in range(jmin, len(C)):
            M = V.copy()
            M[j] += 1
            w = C @ M
            G = greedy_algorithm(C, w)

            if M.sum() < G.sum():
                return (False, w, M)

    return (True, None, None)


C = np.array([140, 84, 63, 10, 1])

is_canonical, w, M = check_canonical(C)

if is_canonical:
    print(f"{C} is canonical")
else:
    print(f"{C} is not canonical (counterexample: {w})")
    print(f"M(w): {M}")
    print(f"G(w): {greedy_algorithm(C, w)}")

感想

適当な会話から発生した話題だったけど、調べてみると結構面白い話題だった。生活の役に立つかは分からないですが、皆さんも身近な通貨体系がcanonicalかどうかが気になって夜も眠れない時があったら計算して求めてみてください。

*1:https://ecommons.cornell.edu/handle/1813/6219

*2:書くのが面倒くさくなってきた