貪欲法

貪欲法

蟻本によれば、

貪欲法とは1つのルールに従って、貪欲的に「その場での最善」を選択することを 繰り返すというアルゴリズム設計手法です。

複数種類のコインを使ってある額のお買い物をし、
コインの枚数を最小にする系の問題ではよく使うらしい。
ただし、コインを問題文で見たからと言って必ずしもそうではない。
参考：硬貨の問題が貪欲法で解けるための条件

例題

• ABC076 B問題
• AOJ ALDS1_15_A

ABC076 B. Addition and Multiplication

問題はこちら

掲示板に書いてある数字を、A, Bいずれかの操作をあわせてN回実施し、
できるだけ最小になるように出力する問題。
とにかく、途中経過の数を最小になるように操作を選べば最小値を出力できる。

#coding:utf-8
#貪欲法
n = int(input())
k = int(input())
ans = 1
#各回で常に答えが最小値になる方の計算を実施する
for i in range(n):
    ans = min(2*ans, ans+k)

print(ans)

AOJ ALDS1_15_A お釣りの最小個数

Aizu Online Judge(AOJ)より。
典型的な問題だと思う。

#coding:utf-8
n = int(input())
coin = [25, 10, 5, 1]
ans = 0

for i in range(0, 4):
    #貪欲法。金額が高いものから使ってお釣りを生成する
    ans += n // coin[i]
    n = n % coin[i]

print(ans)