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

方針：$n=1,2,\dots ,12$ について、貪欲法の枚数 $G(n)$ と動的計画法で求めた最小枚数 $M(n)$ を表にして比べる。

1. 貪欲法の枚数 $G(n)$

できるだけ $5$ 円を使い、残りにできるだけ $4$ 円を使い、最後に $1$ 円を使う。
- $n=1,2,3$：$1$ 円だけなので $G=1,2,3$
- $n=4$：$4$ で $G=1$
- $n=5$：$5$ で $G=1$
- $n=6$：$5+1$ で $G=2$
- $n=7$：$5+1+1$ で $G=3$
- $n=8$：$5+1+1+1$ で $G=4$
- $n=9$：$5+4$ で $G=2$
- $n=10$：$5+5$ で $G=2$
- $n=11$：$5+5+1$ で $G=3$
- $n=12$：$5+5+1+1$ で $G=4$

2. 動的計画法による $M(n)$

最後に使う硬貨が $1$ 円・$4$ 円・$5$ 円のいずれかであることから、$M(0)=0$ とし、
$$M(n)=\min \{M(n-1),M(n-4),M(n-5)\}+1$$
（$n-c<0$ となる項は除く）で順に表を埋める。
- $M(1)=M(0)+1=1$、$M(2)=2$、$M(3)=3$
- $M(4)=\min \{M(3),M(0)\}+1=1$
- $M(5)=\min \{M(4),M(1),M(0)\}+1=1$
- $M(6)=\min \{M(5),M(2),M(1)\}+1=2$
- $M(7)=\min \{M(6),M(3),M(2)\}+1=3$
- $M(8)=\min \{M(7),M(4),M(3)\}+1=\min \{3,1,3\}+1=2$
- $M(9)=\min \{M(8),M(5),M(4)\}+1=2$
- $M(10)=\min \{M(9),M(6),M(5)\}+1=2$
- $M(11)=\min \{M(10),M(7),M(6)\}+1=3$
- $M(12)=\min \{M(11),M(8),M(7)\}+1=\min \{3,2,3\}+1=3$

3. 比較

$G(n)>M(n)$ となるのは $n=8$（貪欲法は $5+1+1+1$ の $4$ 枚、最適は $4+4$ の $2$ 枚）と $n=12$（貪欲法は $5+5+1+1$ の $4$ 枚、最適は $4+4+4$ の $3$ 枚）である。

よって求める $n$ は $\{8,12\}$。

動的計画法で $M(n)$ を求める。$M(0)=0$、$M(n)=1+\min (M(n-1),M(n-4),M(n-5))$（引く数が負にならない範囲）。

$M(1),\dots ,M(12)$ は順に $1,2,3,1,1,2,3,2,2,2,3,3$。

貪欲法の枚数 $G(n)$：
- $n=1,2,3$：$1,2,3$ 枚
- $n=4$：$4$ で $1$ 枚
- $n=5$：$5$ で $1$ 枚
- $n=6$：$5+1$ で $2$ 枚
- $n=7$：$5+1+1$ で $3$ 枚
- $n=8$：$5+1+1+1$ で $4$ 枚（最適は $4+4$ の $2$ 枚）
- $n=9$：$5+4$ で $2$ 枚
- $n=10$：$5+5$ で $2$ 枚
- $n=11$：$5+5+1$ で $3$ 枚
- $n=12$：$5+5+1+1$ で $4$ 枚（最適は $4+4+4$ の $3$ 枚）

$G(n)>M(n)$ となるのは $n=8,12$ である。

検算：$8=4+4$ は $2$ 枚、$12=4\times 3$ は $3$ 枚で、貪欲法の枚数より少ない。他の $n$ では $G=M$ が確かめられた。