[アルゴリズム]Greedy貪欲アルゴリズム

Greedy Algorithm

「それぞれの選択肢の中で、この時点で最適な答えを選択して、適切な結果を得る」

Q . マシュマロ実験(マシュマロを1個与える、食べないなど、2個与える実験)でGriddyアルゴリズムを用いた結果は何ですか?
A . すぐ目の前のマシュマロを食べます.
ただし、待ち時間に2個食べる最適年数は保証できません.
►GRADYアルゴリズムを使用する場合を判断する.

Greedyアルゴリズムを使用する問題

最適な局所構造と貪欲な選択属性の特徴を有する問題

=1回の選択は次の選択に対して全く関係のない値であるべきであり、各瞬間の最適解は問題に対する最適解であるべきである.

典型的な例:おつりの問題

無制限コイン500元100元50元10元が存在していますN元を探す時、必要な硬貨の最小個数がいくらなことを求めます.
「大きな通貨単位から無条件に探す」というアルゴリズムを守れば,常に最適解を保証できる.
[サンプルコード/C+]

#include<bits/stdc++.h>
using namespace std;

int N, ans;

int main() {
	int coins[4] = { 500,100,50,10 };
	cin >> N;
	for (int i = 0; i < 4; i++) {
		cout << coins[i] << "원: " << N / coins[i] << "개\n";
		ans += N / coins[i];
		N %= coins[i];
	}
	cout <<"총 "<< ans << "개";
	return 0;
}

リファレンスサイト
https://blog.naver.com/ndb796/221242106787
https://namu.wiki/w/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://velog.io/@contea95/%ED%83%90%EC%9A%95%EB%B2%95%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98