[貪欲法 欠点]コインの問題と最適解が約束されていないことの証明
先日は「部分問題を最適化して問題を解く」のが貪欲法のポイントであると紹介しました。この方法ならどんな問題でも解けるではないかと思われたかもしれませんが、そんなことはありません。
まずは貪欲法で解ける問題として有名なコインの問題をみていきましょう。
コインの問題
貪欲法の典型例題として、コインの問題があります。たとえば14円支払うのに、硬貨を最小の枚数で支払うには、どの硬貨を何枚組み合わせればよいかを求めるような問題です。
この問題は「硬貨を最小の枚数で支払う」ことの繰り返しで14円支払うという目的を果たす、と読み替えることもできますね。硬貨の枚数を最小にするには、できるだけ大きな硬貨で支払うことで可能になります。
この硬貨を最小の枚数で支払うという部分が貪欲法的ポイントです。
この問題の場合には、10円1枚、1円4枚が答えですね。
貪欲法で解けるかどうかの判定
上記の問題は貪欲法で解けました。日本の硬貨（2021年03月10日現在）を扱った問題だからです。？何が言いたいのかよくわかりませんね。では、もしも、日本硬貨にたとえば7円硬貨が存在していたらどうでしょうか？この場合は、7円2枚が正解なのですが、貪欲法は、できるだけ大きな硬貨で支払うルールなので、10円硬貨から支払いをしてしまいます。なので、この問題を貪欲法で解くことはできません。
しかしながら、コインの問題に関して貪欲法で解けるかどうかを判定する方法があります。
コインの問題は整数ナップサック問題の特殊型であり、整数ナップサック問題が貪欲法で解けるための条件がそのまま適用できるということです。
コインの問題に限定した条件は以下のようになります。
コインを小さい順に
a1,a2,⋯,an
と並べたとき、あるj（1≤j≤n−1）について
a（j+1）=p＊a（j）−δ
となるpとδ（0≤δ<aj）は一意に定まります（割り算の商と余りの式に近い感じです）。
そのpとδに対し、
H(δ)≤p−1
が全てのjについて成り立つことが貪欲法が適用可能な条件です。
ただし、H(x)はx円を支払う場合に貪欲法を用いて求めた最小の硬貨の枚数とします。
では、さきほどの問題にこちらの条件を適用してみましょう。
まず、a（j+1）がa（j）で割り切れる場合を考えます（日本の通貨体系では2000円札を除き、これが当てはまります）。
このとき、明らかにδ=0、H(0)=0で、pは1以上となることから、常に条件が成立します。
次に、硬貨が1円、５円、７円、10円だった場合について確認してみます。
a(j)=7、a(j+1)=10とすると、p=2、δ=4と定まり、
H(δ)=H(4)=4>1=2−1
と、条件が成立しないことが分かります。
つねにこの条件式を適用して問題を解けるかを判定するのも面倒ですが、ざくっと、a（j+1）がa（j）で割り切れる場合を考慮すればよいでしょう。なので、日本硬貨については、1円、5円、10円、５０円、100円、500円なので、すべて割り切れるので、貪欲法が適用可能と考えてよさそうです。
詳細な数学的証明はたとえばこちらの資料をご覧ください。
整数ナップサック問題が多項式時間で解ける特殊な場合を定める条件について飯田浩志∗
実際の貪欲法の問題を解いてみる
日本硬貨をつかった問題を貪欲法で解いてみましょう。
おつり
問題
太郎君はよくJOI雑貨店で買い物をする． JOI雑貨店には硬貨は500円，100円，50円，10円，5円，1円が十分な数だけあり，いつも最も枚数が少なくなるようなおつりの支払い方をする．太郎君がJOI雑貨店で買い物をしてレジで1000円札を1枚出した時，もらうおつりに含まれる硬貨の枚数を求めるプログラムを作成せよ
AOJ : https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0521
たとえばこんな風にかけますね。
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> pays;
while (1) {
int tmp;
cin >> tmp;
if (tmp == 0) {
break;
} else {
pays.push_back(tmp);
}
}
vector<int> coins = {500, 100, 50, 10, 5, 1};//コイン種別の定義
for (auto pay : pays) {
int charge = 1000 - pay; // おつり
int ans = 0;
for (auto coin : coins) { //コインの種別ごとにループ
int use = charge / coin; // コインの使用枚数
charge -= coin * use; //最大のコインでできるだけ支払う
ans += use; //使用したコインの枚数を記録
}
cout << ans << endl;
}
return 0;
}
このように、日本硬貨の問題は貪欲法で解くことができます。
ではでは！