탐욕 알고리즘(greedy algorithm)

1. 탐욕 알고리즘이란?
  - 여러 경우 중 하나를 결정해야 하는 순간마다, 최적의 선택을 진행하여 결과를 구하는 기법
  - 특정 순간에 전체 조합(예, 전체 동전의 조합)을 고려하지 않고 그 순간의 최적의 선택을 시행한다

2. 탐욕 알고리즘의 문제
  1. 최소 동전 개수 구하기
    - 주어진 금액을 지불해야 할 때, 동전을 가장 적게 사용해 지불할 수 있는 경우 찾기
    - 가장 큰 금액의 동전을 사용해 최대한 많이 지불하는 것이 매순간(지금 이 순간) 가장 좋은 선택!

coin_list = [1,50,500,100]

def count(value, coin_list):
    total_count = 0
    details = list()
    coin_list.sort(reverse = True)
    for coin in coin_list:
        coin_num = value // coin
        value -= coin * coin_num
        total_count += coin_num
        details.append([coin, coin_num])
    return total_count, details

a = count(4720, coin_list)
print(a)

  2. 부분 배낭 문제 (Fractional Knapsack Problem)
    - 무게 제한(capacity)을 가지는 배낭이 최대 가치를 갖도록 물건을 넣는 문제
    - 물건을 쪼갤 수 있어 일부분만 배낭에 넣을 수 있다 (Fractional을 쓰는 이유)

data = [(10,10), (15,12), (20,10), (25,8), (30,5)]

def get_max_value(data, capacity):
    """ 무게 대비 가치를 키로 두고 내림차순 정렬 """
    data = sorted(data, key=lambda x: x[1]/x[0], reverse=True)
    total_value = 0
    details = list()

    for d in data:
        if capacity - d[0] >= 0:
            capacity -= d[0]
            total_value += d[1]
            details.append([d[0], d[1], 1])
        else:
            fraction = capacity / d[0]
            total_value += d[1] * fraction
            details.append([d[0], d[1], fraction])
            break
    return total_value, details

print(get_max_value(data, 30))

 

출처 : fastcampus