8 最適解

前節の命題 8 により、 下の額から切り分け、ある額以下の硬貨で分割できる場合には それぞれで最適化を考えればいいことがわかった。 例えば、代金 $x$ が 337 円で、財布 $H$ に 544 円ある場合は、

• 1 円玉以下 : $x$ は 2 円、$H$ は 4 円なので、ここでまず分割する ($x_1=2$, $H_1=F_M(4)$)。残りは $x$ は 335 円、$H$ は 540 円。
• 5 円玉以上で 5 円玉以下 : $x$ は 5 円、$H$ 0 円なので分割できない。
• 5 円玉以上で 10 円玉以下 : $x$ は 35 円、$H$ 40 円なので、 ここで分割できる ($x_2=35$, $H_2=F_M(40)$)。 残りは $x$ は 300 円、$H$ は 500 円。
• 50 円玉以上で 50 円玉以下 : $x$ は 0 円、$H$ は 0 円なので ここは考えなくてよい。
• 100 円玉以上で 100 円玉以下 : $x$ は 300 円、$H$ は 0 円なので 分割できない。
• 100 円玉以上で 500 円玉以下 : $x$ は 300 円、$H$ は 500 円なので ここで分割 ($x_3=300$, $H_3=F_M(500)$)。

これにより、 $x=x_1+x_2+x_3$, $H=H_1\mathrel{\oplus}H_2\mathrel{\oplus}H_3$ と分割され、そのそれぞれ $H_k$ と $x_k$ で最適解を考えればよいことになる。

しかも、$x_2$ と $H_2$、$x_3$ と $H_3$ は、 下の方の額の硬貨がないので、 その分を全体で割った硬貨系での最適化と同じことになる。 すなわち、$x_2=35$ 円を $H_2=F_M(40)$ 円で払う問題は、 全体を 5 で割った 1 円玉と 2 円玉の硬貨系で、 「1 円玉 1 枚と 2 円玉 3 枚 の 7 円」を、 「2 円玉 4 枚」の中から支払う問題と同じことになるし、 $x_3=300$ 円を $H_3=F_M(500)$ 円で払う問題は、 100 で割った 1 円と 5 円の硬貨系で、 「1 円玉 3 枚の 3 円」を「5 円玉 1 枚」の中から支払う問題と同じになる。

このように考えると、それぞれの分割単位での最適解を求める問題は、 代金の一番低い額の硬貨成分 $n_{j_1}(X)$ は常に正であると仮定し、 $H$ で下から分割ができない場合のみを考えればいいことになる。

命題 9.

$\mathrm{Tot}(H)\geq x$, $X=F_M(x)$ で $n_{j_1}(X)>0$ のとき、 命題 8 のように分割できないのは、 以下の 2 つを満たす形の場合である。

• $n_{j_1}(X)>n_{j_1}(H)$
• $X$ の最高位の硬貨を $j_n$ とするとき、 $j_1<j<j_n$ のすべての $j$ に対して $n_j(X)\geq n_j(H)$

なお、最高位の $n_{j_n}(X) (>0)$ と $n_{j_n}(H)$ との間には 特に条件はない。 例えば、$x=224$ 円で $\mathrm{Tot}(H)=313$ 円の場合 ( $n_{j_n}(X)<n_{j_n}(H)$) もあれば、 $x=224$ 円で $\mathrm{Tot}(H)=513$ 円の場合 ( $n_{j_n}(X)>n_{j_n}(H)$) もあれば、 $x=224$ 円で $\mathrm{Tot}(H)=713$ 円の場合 ( $n_{j_n}(X)=n_{j_n}(H)$) もありうる。

証明

もし、 $n_{j_1}(X)\leq n_{j_1}(H)$ ならば最下位 の $j_1$ で 分割ができてしまうので、 $n_{j_1}(X) < n_{j_1}(H)$ でなければならない。

その上の額でも、$j<j_n$ で $n_j(X)<n_j(H)$ となる $j$ があれば $(n_j(X)+1)$ 個の $j$ 円の $H$ の硬貨で $j$ 以下の $X$ の金額を越え、 やはりそこで分割できてしまうことになるので、 $j_1<j<j_n$ のすべての $j$ に対して $n_j(X)\geq n_j(H)$ でなければならない。

逆に、その両者が満たされていれば、 下から見てどこで止めても $X$ の額の方が $H$ の額を上回るので 分割はできないことは明らか。

よって後は命題 9 を満たす形式の $x$, $H$ の場合の 最適化問題を解けばよいのだが、この場合解答は容易である。

命題 10.

命題 9 を満たす $x$, $H$ に対する最適化解 $P$ は、 $X$ の最上位部分のみを一つ増やした額 $x'=(n_{j_n}(X)+1)j_n$ に 対する最適解に等しい。

この命題は、例えば $x=224$ 円で $\mathrm{Tot}(H)=313$ 円、 $\mathrm{Tot}(H)=513$ 円、 $\mathrm{Tot}(H)=713$ 円等の場合は、 いずれも $x'=300$ 円に対する最適な支払いをすればよいことを意味する。 すなわち $\mathrm{Tot}(H)=313$ 円の場合は 300 円 ($x'$ 丁度) が、 $\mathrm{Tot}(H)=513$ 円の場合は 500 円 ($x'$ の極小解) が、 $\mathrm{Tot}(H)=713$ 円の場合は 500 円が、 それぞれ最適な支払いとなる。 これも、多分日常的な感覚とはそれほどずれていない自然な解だと思われる。

証明

Step 1. まず、$j_n$ より下の硬貨は払えないことを示す。

$j_1$ の硬貨は最大でも $n_{j_1}(H)$ しか払えず、 これは $n_{j_1}(X)$ より小さいので、 上から借りなければ支払えない。 よって、$j_1$ のおつりは、

$$n_{j_1}(R) = N_{j_1} + n_{j_1}(P) - n_{j_1}(X) = (N_{j_1} - n_{j_1}(X)) + n_{j_1}(P)$$

となるが、最後の右辺の最初の項は常に正なので、 $n_{j_1}(R)>0$ となる。 よって、仮定 5 により $n_{j_1}(P)=0$ でなければならない。

次は $j=j_2,j_3,\ldots$ を帰納的に考えると、 $j$ の硬貨は一つ下の額の硬貨に貸しておつりを作っているので、 $n_j(P) (\leq n_j(H)\leq n_j(X))$ から一つ減ることになり、 やはり $n_j(X)$ を払うことはできず、上から一つ借りなければいけない。 よって、$j$ のおつりは、

$$n_j(R) = N_j + n_j(P) - 1 - n_j(X) = (N_j - n_j(X) - 1) + n_j(P)$$

となるが、この右辺の最初の項は 0 以上なので、$n_j(P)>0$ だと $n_j(R)$ と $n_j(P)$ の両者が正となり、 やはり仮定 5 に反する。

よって、$j<j_n$ では $n_j(P)=0$ でなければならない。

Step 2. 次に $j_n$ 以上を含めた支払いについて考える。

Step 1. により、$P$ は $j_n$ 以上の硬貨の支払いのみが 可能なことになるが、この場合は、どのように払っても $j_n$ 未満のおつりは同じであり、 しかも、それは一つ $j_n$ を借りなければ支払えないので、 そのおつり $R_1$ は、$j_n$ 未満の $X$ を $j_n$ で払った おつりとなる。

その下位のおつりのために、$P$ は、

$$\mathrm{Tot}(P)-j_n \geq n_{j_n}(X) j_n$$

でなければならず、よって $P$ は、

$$\mathrm{Tot}(P)\geq n_{j_n}(X) j_n + j_n$$

で、$P$ で $(n_{j_n}(X) j_n + j_n)$ を払ったおつりを $R_2$ とすると、 $x$ を $P$ で払ったおつり $R$ は $R=R_1\mathrel{\oplus}R_2$ となる。

$R_1$ は $P$ にはよらないので、結局 $P$ は、 $(n_{j_n}(X) j_n + j_n)$ の支払い (とおつり $R_2$) を 最適にするものになる。

お札を一枚借りる場合も同じで、 命題 5 よりお札を借りなくて済むのであれば そういう解が最適なはずだし、 よってお札を借りる解が最適の場合は、 $H$ が $x$ には足りない場合なので、 どのような解も札を 1 枚借りることになる。 よって、それを硬貨と考えて最適解を求め、それを札に戻しても、 他の解との関係性 (それが最適であるという関係) に変化はない。

また、この命題 10 のいう最適解は、 命題 7 より一意的であることがわかる。 すなわち、$x'$ を支払う丁度の解か、 そうでなければ $j_n$ より大きくて $H$ に含まれる最も小さい額の硬貨 1 枚の極小解が最適解だということがわかる。 つまり、これにより次の命題 11 も証明できたことになる。

命題 11.

最適解は一意的であり、 それ以外の解は必ず最適解より小銭の枚数が増えることになる。

例えば、この節の最初に上げた、$x=337$ 円、$H$ が 544 円の場合は、 $x_1=2$ 円に対しては $\mathrm{Tot}(P_1)=2$ 円が最適解。 $x_2=35$ 円に対しては $\mathrm{Tot}(P_2) = 40 円$ が $x_2'=40$ 円の最適解。 $x_3=300$ 円に対しては $\mathrm{Tot}(P_3) = 500 円$ が最適解となる。 よって、この場合の最適解は、支払いが $P=P_1\mathrel{\oplus}P_2\mathrel{\oplus}P_3$ の 542 円で、 おつり $R$ が 205 円、となる。