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

手順 1：動的計画法で $M(n)$ を求める。

$M(0)=0$ とし、$n\ge 1$ に対して
$$M(n)=\min \{M(n-c)+1\mid c\in \{1,3,4\},c\le n\}$$
で表を埋める。最後に使う硬貨を $c$ 円とすると、残り $n-c$ 円は最小枚数で払うのが最善なので、この漸化式が成り立つ。

• $M(1)=M(0)+1=1$
• $M(2)=M(1)+1=2$
• $M(3)=\min \{M(2),M(0)\}+1=1$
• $M(4)=\min \{M(3),M(1),M(0)\}+1=1$
• $M(5)=\min \{M(4),M(2),M(1)\}+1=2$
• $M(6)=\min \{M(5),M(3),M(2)\}+1=2$
• $M(7)=\min \{M(6),M(4),M(3)\}+1=2$
• $M(8)=\min \{M(7),M(5),M(4)\}+1=2$
• $M(9)=\min \{M(8),M(6),M(5)\}+1=3$
• $M(10)=\min \{M(9),M(7),M(6)\}+1=3$
• $M(11)=\min \{M(10),M(8),M(7)\}+1=3$
• $M(12)=\min \{M(11),M(9),M(8)\}+1=3$

手順 2：貪欲法で $G(n)$ を求める。

大きい硬貨から使えるだけ使う。

• $n=1,2,3,4$：$1$、$1+1$、$3$、$4$ なので $G=1,2,1,1$
• $n=5$：$4+1$ で $G(5)=2$
• $n=6$：$4+1+1$ で $G(6)=3$
• $n=7$：$4+3$ で $G(7)=2$
• $n=8$：$4+4$ で $G(8)=2$
• $n=9$：$4+4+1$ で $G(9)=3$
• $n=10$：$4+4+1+1$ で $G(10)=4$
• $n=11$：$4+4+3$ で $G(11)=3$
• $n=12$：$4+4+4$ で $G(12)=3$

手順 3：比べる。

$n=1,\dots ,12$ で $G(n)$ と $M(n)$ を比べると、異なるのは次の $2$ つだけである。

• $n=6$：$G(6)=3$、$M(6)=2$（$3+3$）
• $n=10$：$G(10)=4$、$M(10)=3$（$3+3+4$）

それ以外の $n$ では $G(n)=M(n)$ である。

よって、求める $n$ は $\{6,10\}$ である。

硬貨は 1, 3, 4 円。まず最小枚数 $M(n)$ を動的計画法 $M(n)=1+\min (M(n-1),M(n-3),M(n-4))$ で求める（$M(0)=0$）。

$M(1)=1,M(2)=2,M(3)=1,M(4)=1,M(5)=2(4+1),M(6)=2(3+3),M(7)=2(3+4),M(8)=2(4+4),M(9)=3,M(10)=3(3+3+4),M(11)=3(4+4+3),M(12)=3(4+4+4)$。

次に貪欲法の枚数 $G(n)$ を求める。
$G(1)=1,G(2)=2,G(3)=1,G(4)=1,G(5)=2(4+1),G(6)=3(4+1+1),G(7)=2(4+3),G(8)=2(4+4),G(9)=3(4+4+1),G(10)=4(4+4+1+1),G(11)=3(4+4+3),G(12)=3(4+4+4)$。

比較すると、$G(n)>M(n)$ となるのは $n=6$（3>2）と $n=10$（4>3）のみ。

検算：$6=3+3$ は 2 枚、$10=3+3+4$ は 3 枚で、貪欲法の枚数より少ない。他の $n$ では $G(n)=M(n)$ を上の表で確認した。