アルゴリズムと計算量の問題

方針：動的計画法で最小枚数 $M(n)$ の表を作り、貪欲法の枚数 $G(n)$ と並べて比べる。

手順 1：$M(n)$ を動的計画法で求める。
$M(0)=0$ とする。$n\ge 1$ のとき、最後に使う硬貨 $c\in \{1,4,6\}$（ただし $c\le n$）で場合分けすると、残り $n-c$ 円は最小枚数で払えばよいので
$$M(n)=\underset{c}{\min }\{M(n-c)+1\}$$
が成り立つ。これで順に表を埋める。
- $M(1)=1,M(2)=2,M(3)=3$（$1$ 円硬貨のみ使える）
- $M(4)=\min \{M(3)+1,M(0)+1\}=1$
- $M(5)=\min \{M(4)+1,M(1)+1\}=2$
- $M(6)=\min \{M(5)+1,M(2)+1,M(0)+1\}=1$
- $M(7)=\min \{M(6)+1,M(3)+1,M(1)+1\}=2$
- $M(8)=\min \{M(7)+1,M(4)+1,M(2)+1\}=\min \{3,2,3\}=2$
- $M(9)=\min \{M(8)+1,M(5)+1,M(3)+1\}=\min \{3,3,4\}=3$
- $M(10)=\min \{M(9)+1,M(6)+1,M(4)+1\}=\min \{4,2,2\}=2$
- $M(11)=\min \{M(10)+1,M(7)+1,M(5)+1\}=\min \{3,3,3\}=3$
- $M(12)=\min \{M(11)+1,M(8)+1,M(6)+1\}=\min \{4,3,2\}=2$

手順 2：$G(n)$ を求める。
大きい硬貨から使えるだけ使う。
- $n=1,2,3$：$1$ 円だけで $G=1,2,3$
- $n=4$：$4$ で $G=1$、$n=5$：$4+1$ で $G=2$
- $n=6$：$6$ で $G=1$、$n=7$：$6+1$ で $G=2$
- $n=8$：$6+1+1$ で $G=3$
- $n=9$：$6+1+1+1$ で $G=4$
- $n=10$：$6+4$ で $G=2$
- $n=11$：$6+4+1$ で $G=3$
- $n=12$：$6+6$ で $G=2$

手順 3：比べる。
$n=1,\dots ,7$ と $n=10,11,12$ では $G(n)=M(n)$ である。
一方、
- $n=8$：$G(8)=3>M(8)=2$（最適は $4+4$）
- $n=9$：$G(9)=4>M(9)=3$（最適は $4+4+1$）

よって求める $n$ は $\{8,9\}$ である。

硬貨 $1,4,6$ について、各 $n$ の $M(n)$ と $G(n)$ を順に求める。

• $n=1$: $M=1$, $G=1$
• $n=2$: $M=2$, $G=2$
• $n=3$: $M=3$, $G=3$
• $n=4$: $M=1$, $G=1$
• $n=5$: $M=2$ ($4+1$), $G=2$
• $n=6$: $M=1$, $G=1$
• $n=7$: $M=2$ ($6+1$), $G=2$
• $n=8$: $M=2$ ($4+4$)。貪欲法は $6+1+1$ で $G=3$。よって $G>M$。
• $n=9$: $M=3$ ($4+4+1$)。貪欲法は $6+1+1+1$ で $G=4$。よって $G>M$。
• $n=10$: $M=2$ ($6+4$), $G=2$
• $n=11$: $M=3$ ($6+4+1$), $G=3$
• $n=12$: $M=2$ ($6+6$), $G=2$

$M(n)$ は、$n=9$ で $2$ 枚以下の組が作れないことなども確かめた。たとえば $9$ は、$2$ 枚の和が $9$ になる硬貨の組が存在しない。

したがって $G(n)>M(n)$ となるのは $n=8,9$ である。