貪欲算法と列挙法について

質問

今ナップサック問題をやっているのですが
疑問に思ったので質問します

貪欲算法の方が数が多いとき速く答えが出る、
ということは分かりますが、他にも貪欲法の
利点または欠点はありますか。ぎゃくに
列挙法の方がよいことがありますか

回答No.1

kony0 · ベストアンサー

貪欲算法がなにを差しているか、多少類推がありますが・・・あと、まとはずれな言動かもしれません。その場合はお許しください。

３種類の品物がじゅうぶん多数個あって、
品物Ａ：価値１２、重さ６、単位重量あたり価値２．０
品物Ｂ：価値　９、重さ５、単位重量あたり価値１．８
品物Ｃ：価値　５、重さ４、単位重量あたり価値１．２５
とします。いまナップサックの容量が重さ１０までしか耐えられないとすると、
単位重量あたり価値が最も高いＡを１つ入れてしまい、残りの容量でＣを入れるよりも、当然にＢを２つ入れたほうが総価値は高いですよね。

ナップサック問題が離散的である限り、単純に単位あたり価値の最も高い順に採用していく方法が、厳密に最適な解を求められるわけではない、というので貪欲法の欠点の指摘ということでよろしいでしょうか？