厳密解（最適解）が求まらない例
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/05/18 13:51 UTC 版)
「貪欲法」の記事における「厳密解（最適解）が求まらない例」の解説
以下にナップサック問題での適用例を示す。この問題の場合は各荷物ごとに分割して評価することで適用可能である。 ナップサック問題の各荷物の評価値を決定する。（価値）÷（容積）という数字がよく使われる。 評価値の一番高い荷物を選ぶ。 その荷物をナップサックに入れても最大容量を越えないならナップサックに入れる。 全ての荷物を評価値の順に選び上記の操作を繰り返す。 なお、この問題に関しては貪欲法では最適解を得られない。
※この「厳密解（最適解）が求まらない例」の解説は、「貪欲法」の解説の一部です。
「厳密解（最適解）が求まらない例」を含む「貪欲法」の記事については、「貪欲法」の概要を参照ください。
ウィキペディア小見出し辞書の「厳密解が求まらない例」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 厳密解が求まらない例のページへのリンク
