탐욕알고리즘(Greedy)

탐욕알고리즘이란?

- 최적의 해에 가까운 값을 구하기 위해 사용됨

- 여거 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 ,최종적인 값을 구하는 방식

 

탐욕 알고리즘의 예

문제1 : 동전문제

지불해야한느 값이 4720원 일 때 1원 50원 100원 500원 동전으로 동전의 수가 가장 적게 지불하기오.

- 가장 큰 동전부터 최대한 지불해야하는 값을 채우는 방식으로 구현가능

- 탐욕알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨

 

 

해결방법

coin_list = [500, 100, 50, 1]

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

 

문제2 : 부분 배낭 문제

무게제한이 k인 배낭에 최대가치를 가지도록 물건을 넣는 문제

- 각 물건은 무게와 가치로 표현될 수 있음

- 물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있음, 그래서 Fractional Knapsack Problem으로 부름

물건(i)	물건1	물건2	물건3	물건4	물건5
무게(w)	10	15	20	25	30
가치(v)	10	12	10	8	5

 해결방법

data_list = [(10,10), (15,12), (20,10), (25,8), (30,5)]
def get_max_value(data_list, capacity)
    data_ilst = sorted(data_list, key = lambda x:x[1]/x[0], reverse=True)
    total_value = 0
    details = list()
    
    for data in data_list:
        if capacity - data[0] >= 0:
            capacity -= data[0]
            total_value = data[1]
            details.append([data[0],data[1],1])
        else:
            fraction = capacity / data[0]
            total_value += data[1] * fraction
            details.append([data[0],data[1],fraction])
            break
    return total_value, details