[알고리즘] 그리디 - 배낭 문제 (Python)

 

 

---

문제 설명

배낭에 담을 수 있는 무게의 최댓값이 정해져있고, 각각의 짐의 가치($ 단위)와 무게(kg 단위)가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록, 즉 $(달러)의 가치가 최대가 되도록 짐을 고르는 방법을 찾기

분할 가능한 배낭 문제

 

입출력 예

Input:

cargo = [
    (4, 12),
    (2, 1),
    (10, 4), 
    (1, 1),
    (2, 2),
]

Output:

17.333333333333332

 

Code

def fractional_knapsack(cargo):
    capacity = 15
    pack = []
    # 단가 계산 역순 정렬
    for c in cargo:
        pack.append((c[0] / c[1], c[0], c[1]))
    pack.sort(reverse = True)
    
    # 단가 순 그리디 계산
    total_value: float = 0
    for p in pack:
        if capacity - p[2] >= 0:
            capacity -= p[2]
            total_value += p[1]
        else:
            fraction = capacity / p[2]
            total_value += p[1] * fraction
            break
    
    return total_value

이 문제는 로컬 최적값으로부터 글로벌 최적값을 도출해내는 그리디 알고리즘을 적용해 풀 수 있다. 우선 pack 리스트에 각 짐의 kg 당 가치 (단가)를 포함한 정보들을 할당한다. 이때, 단가가 높은 짐부터 넣는 것이 가장 효율적이므로, pack의 순서를 역순으로 뒤집는다. 이후, 주어진 제한 kg (capacity) 이내에서 단가가 높은 순서대로 짐을 packing하다가 짐 하나를 전부 넣을 수 없는 순간에는 fraction (capacity / 짐의 무게)의 비중으로 짐을 packing하고, 가치를 계산해준다. 이 문제는 짐을 분할할 수 있다는 점에서 그리디 알고리즘으로 풀 수 있었다. 

 

---

 

 

I'm a Senior Student in Data Science ! 

데이터 사이언스를 공부하고 있는 학부생의 TIL 블로그입니다. 게시글이 도움 되셨다면 구독과 좋아요 :)