[アルゴリズム]貪欲/貪欲なアルゴリズム

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

欲張り/グリディアルゴリズム

  • 動的計画法とは異なり,将来を考慮せずに各段階で最適な選択を行う方法である.△私は各段階で最善の選択をして、全体的に最高であることを望んでいます.
  • は、すべての場合に使用できるアルゴリズムではありません.
  • の最適解を求めるために使用される.(ただし、これは最適な年を保証するものではありません...)
  • 階調アルゴリズムは、ソートとともに使用される.

    • 貪欲/グリディアルゴリズムの原理



    (出典:https://en.wikipedia.org/wiki/File:Greedy-search-path-example.gif)

    Python実行コード


    ex)会議室がありますが、n個の会議を使うと重複しません。会議室が最大で使える場合は、数を見つけてください。

    # input:
5
1 5
2 3
3 5
4 7
5 8
    import sys
sys.stdin=open("input.txt", "r")
n = int(input())
a = []
for i in range(n):
    b = list(map(int, input().split()))
    a.append(b)
a.sort(key=lambda x: (x[1], x[0]))
end = 0
cnt = 0
for i in range(n):
    if end <= a[i][0]:
        end = a[i][1]
        cnt += 1
print('최대수 : {}'.format(cnt))
# 최대수 : 3
    GBKとUTF-8の荒い判断
    [白俊]2178号迷宮探索/Java,Python