알고리즘(1) - 그리디

- 최적의 해에 가까운 값을 구하는 방법이나, 최적의 해라고 확신할 수는 없음 (근사치 추정) => 한계
- 매 순간 최적이라고 생각되는 경우 한 가지를 선택하는 방법
- 동적 계획법의 computation complexity를 극복하기 위해 나온 기법

 

1.  동전 문제

 

    - 최종 지불 가격 = 4720
    - 1원, 50원, 100원, 500원 동전을 가지고 최소한의 동전 개수로 지불하는 방법
    
    => 가장 큰 동전으로 먼저 지불하고, 남은 금액이 해당 동전보다 적은 경우 다음 동전으로 지불하는 방식
    => 그러면 일단 동전의 크기가 큰 순서대로 sorting

 

def paiedCoin(coins, pay):
    result = list()
    count = 0
    coins.sort(reverse = True)  # 큰 순서대로 sorting
    
    for c in coins:
        num = pay//c
        count += num
        pay -= num*c
        result.append([c,num])
    
    return count, result
        

coins = [1,50,100,500]
pay = 4720
paiedCoin(coins, pay)

 

 

2.  부분 배낭 문제 (Fractional Knapsack Problem)

 

    ** 물건을 쪼개서 넣을 수 없는 배낭 문제는 "0/1 Knapsack problem"이라고 함
    
    - 무게 제한이 k인 배낭에 최대 가치를 가지도록 문제를 넣는 문제
    - 각 물건) 무게(w) & 가치(v)
    - 최대의 가치를 담으려면, v/w 가 큰 순서대로 sorting

 

def FracKnapsack(items, size):
    fin_value = 0
    result = dict()
    items.sort(reverse = True ,key = lambda k : k[2]/k[1]) #무게 대비 가치가 높은 순 서대로 정렬
    
    for item in items:
        if size - item[1] >= 0:    
            size -= item[1]
            fin_value += item[2]
            result[item[0]] = 1   # 1 => 100% 다 넣었다는 의미
        
        else:
            fin_value += (item[2]/item[1])*size
            result[item[0]] = size/item[1]   # size/item[1] % 만큼 넣었음
            break  
            # else문으로 들어왔다는 것은, 이 계산 후에 더 이상 넣을 공간이 없다는 것
            # 다음 for문 진행을 하지 않아도 되므로 break
       
    return fin_value, result