貪欲法とは
どんよくほう
各段階で、その時点で最もよく見える選択を1つ選び、後から見直さずに解を組み立てるアルゴリズムの設計方法。速くて単純だが、最適解が得られるのは、硬貨の組み合わせが日本の硬貨のような場合や、最小全域木のクラスカル法のように、問題が特別な性質を持つときに限られる。
「貪欲法」は、1分野の2問の練習問題に出てきます(データ構造とアルゴリズムなど)。
この用語の分野: データ構造とアルゴリズム
貪欲法の練習問題に挑戦
1円、4円、6円の3種類の硬貨で8円を支払う。大きい硬貨から使えるだけ使う貪欲法で決めたときの枚数と、最少の枚数の関係として正しいものはどれか。
- A貪欲法でも最少の2枚になる
- B貪欲法では3枚になり、最少の2枚にならない
- C貪欲法では3枚になり、これが最少である
解説の中の「貪欲法」
貪欲法では、まず6円を1枚使い、残り2円を1円2枚で払うので3枚です。
1円、4円、6円の3種類の硬貨で8円を支払う。大きい硬貨から使えるだけ使う貪欲法で決めたときの枚数と、最少の枚数の関係…重さあたりの価値の高い順に詰める貪欲法では、重さ2と3(価値7)を入れた後に残り3の容量に入る品物がなく、7で止まります。
容量8のナップサックに、(重さ, 価値) が (2, 3)、(3, 4)、(4, 5)、(5, 6) の4つの品物から…
「貪欲法」が出てくる問題(2問)
データ構造とアルゴリズムの参考書を探す PR
Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。