[アルゴリズム]グリディ

出典これがコードテスト[羅東彬]
今は良いものだけを選んだグリディ.
Greedyアルゴリズムは単純で強力な問題解決方法である.国内でも貪欲法と呼ばれています.名前のように単純に貪欲に解くアルゴリズム.では、貪欲に解決するとはどういう意味でしょうか.
今の状況では、今は良いものだけを選ぶ方法です.
一刻ごとに最善の選択をして、今の選択が後に与える影響を考慮しません.グリディアルゴリズムタイプの問題は創造力が必要であり、少なくとも問題を解決する考えが必要である.そのため、今の状況では、一番よく見えるものだけを選んで、問題を解決できるかどうかを知るべきです.
特長
グリディアルゴリズムは、標準に基づいて最適(適切)なアルゴリズムを選択する.だから問題では、「最大の順序で」「最小の順序で」のように、知らず知らずのうちに基準が与えられている.一般に、この基準はソート時に満たすことができるので、ソートアルゴリズムとペアを組むことが多い.
金をさがす

グリディアルゴリズム問題を用いて最も代表的なお金探し問題を研究した.
質問する
おつりとして使う500元、100元、50元、10元のものは無限に存在します.このとき、お客様に渡すお金がN元の時に探すコインの最低個数です.しかし、探しているお金Nはいつも10の倍数です.
解説
簡単なアイデアさえ思いつけば、問題は解決できる.
「最大通貨単位」から探します.
初めてN元から500元まで探して、それから順番に100元、50元、10元のコインを探します.では、最小のコインの個数はすべて戻ってきます.
例
入力Nが1260の場合は、次の手順で遡及できます.

残金:1260元

顧客
Step 1)1260元から500元の1000元、すなわち500元の2個、残りの260元.

残りのお金:260元

顧客:500元、500元
ステップ2)260ウォンから100ウォン台まで遡り、残りは200ウォン、残りは60ウォン.

残りのお金:60元

顧客:500元、500元、100元、100元
手順3)60元から50元を取り戻し、残りは10元とする.

残りのお金:10元

顧客:500元、500元、100元、100元、50元

ソースコード
パイ

n = int(input())
count = 0

# 큰 단위 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]

for coin in coin_types:
	count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전 개수 세기
	n %= coin

print(count)

C言語

#include <stdio.h>

int main() {
	int n, count = 0;
	int coinTypes[4] = {500, 100, 50, 10};
	scanf("%d", &n);
	
	for(int i = 0; i < 4; i++) {
		count += n / coinTypes[i];
		n %= coinTypes[i];
	}
	
	print("%d", count);

	return 0;
}

グリディアルゴリズムの合理性
すべてのアルゴリズム問題がGRADYアルゴリズムを使用できるわけではない.多くの場合、グリディアルゴリズムを使用すると、「最適解」が見つからないことが多い.しかし、お金を探す問題では、「最大の通貨単位から」お金を探すように、貪欲に近づくと正しい答えが見つかることを保証すれば、非常に効果的で直感的です.
GRADYアルゴリズムで小銭問題を解決できるのは,持っている硬貨のうち,大きい単位は常に小さい単位の倍数であるため,小さい単位の硬貨を総合して他の年を行うことができないためである.
たとえば、通貨単位が500、400、100元で、探しているお金が800元だとします.このとき、グリディアルゴリズムは4枚のコイン(500+100+100+100)を取り戻す必要がある.しかし、最良の年はコイン2枚(400+400)を取り戻すことだ.
グリディアルゴリズムの問題は問題を解決する方法を考え出し、それが正当かどうかを研究しなければならない.
GRADYアルゴリズムの問題を解く
1.2839号:砂糖を送る
2839号：砂糖配達
2.1931号:会議室の手配
1931号:会議室の手配