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

1839 ワード
アルゴリズム#アルゴリズム# python テキストリンク

グレースケールアルゴリズム


グリディアルゴリズムは簡単だが強力な問題解決方法である.
単語に従って翻訳するのは貪欲な方法だ.
この部分では、貪欲さは「今の状況では、今から良いものを選ぶ方法」です.
このアルゴリズムは、後で与える影響を考慮せずに、常に最良に見えるものだけを選択します.
おつりの例
レストランの会計を手伝う店員になったとします.
500元、100元、50元、10元のコインは無限に存在します.お客様に渡すお金がN元である場合、お探しのコインの最低個数を求めます.
△でも、おつりはいつも10の倍数です.
このとき、単純に가장 가격이 큰 동전からお金を探します.
これならN元に設定した価格をすぐに0元に下げるのが適当です.
coin.py
n = 1260 # 거슬러줘야할 가격
count = 0 # 코인의 개수

# 화폐 단위가 큰 것부터 차례로 거슬러준다.
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin # 원래 가격을 코인값으로 나눈 몫만큼 동전으로 추가해줌
    n %= coin

print(count)
通貨種がK個の場合、上記ソースの時間的複雑度はBigOマーキング法でO(K)である.時間の複雑さで総通貨Nが見つからない.
したがって,このアルゴリズムはコインの種類の影響のみを受け,取り戻すべき金額に焦点を当てることはできない.
アルゴリズム問題のタイプを正確に把握することが難しい場合は,グリディアルゴリズムを疑うことができる.
グリディアルゴリズムの例をもっと作ります.
文字列圧縮
【俺用メモ】Linuxのコマンドラインでよく使いそうなの