[자료구조/알고리즘 이론] 냅색 문제(Knapsack Problem)

냅색 문제

냅색 문제는 최적의 조합을 찾기 위한 일종의 최적화 문제입니다. 냅색문제의 기본 개념은 주어진 물품들을 배낭에 담아 최대 가치를 얻는 것입니다. 아래와 같은 15kg 무게 한도의 배낭이 있을 때, 무게 한도 내로 물품을 가방에 넣는다는 가정하에 물건 가치의 합이 최대가 되게 담는 것입니다.

https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C

 

냅색 문제는 몇 가지 변형이 존재하는데, 문제의 변형 형태에 따라 사용할 수 있는 알고리즘이 다릅니다. 냅색 문제의 대표적인 형태는 2가지가 있습니다.

 

분할 냅색 문제(Fractional Knapsack Problem)

- 물품을 쪼개서 배낭에 담을 수 있습니다.

- 무게당 가치가 높은 물품을 우선적으로 담으면 됩니다.

- 가치 높은 물품을 우선적으로 담기만 하면 되기 때문에 그리디 알고리즘(Greedy Algorithm)을 사용합니다.

 

아래와 같은 15kg를 담을 수 있는 배낭, 그리고 열 수 있는 상자에 각각 금괴가 담겨있는 상황을 고려해 봅시다. 배낭의 무게 한도를 초과하지 않으면서 담는 금괴의 가치합을 최대화하기 위해서는 상자의 금괴 kg당 가치를 고려해야 할  것입니다. 

1. 상자 C의 금괴(kg당 $2.5)를 배낭에 담습니다. (남은 배낭의 무게: 11kg)

2. 상자 B의 금괴(kg당 $2)를 배낭에 담습니다. (남은 배낭의 무게: 10kg)

3. 상자 E의 금괴(kg당 $1)를 배낭에 담습니다. (남은 배낭의 무게: 8kg)

4. 상자 D의 금괴(kg당 $1)를 배낭에 담습니다. (남은 배낭의 무게: 7kg)

5. 상자 A의 금괴(kg당 $0.3)를 배낭에 담습니다.

 

마지막 상자 A의 경우 모두 담으면 배낭의 무게한도가 초과되기 때문에 금괴를 분할해서 일부만 담았습니다. 결과적으로 배낭에는 C 4kg, B 1kg, E 2kg, D 1kg, A 7kg가 담겼습니다. 이처럼 물품을 분할해서 일부만 저장할 수 있는 것이 분할 냅색 문제의 특징이며, 이러한 특징 덕분에 그리디 알고리즘을 활용할 수 있습니다. 

 

분할 냅색 문제 코드

# fractional knapsack
def fractional_knapsack(items, capacity):
    items.sort(key=lambda x: x[1]/x[0], reverse=True)
    
    total_value = 0
    
    for weight, value in items:
        if capacity - weight < 0:
            value_per_weight = value // weight
            total_value += value_per_weight * capacity
            break
        else:
            capacity -= weight
            total_value += value
            
    return total_value

i = [(12, 4), (1, 2), (4, 10), (1, 1), (2, 2)]
c = 15
print(fractional_knapsack(i, c))

 

0-1 냅색 문제(0-1 Knapsack Problem)

- 물품을 배낭에 포함시키거나(1) 포함시키지 않는(0) 경우 두 가지만 선택합니다.

- 물품을 쪼갤 수 없습니다.

 

0-1 냅색 문제는 위의 분할 냅색 문제와 다르게 물품을 분할하여 배낭에 담을 수 없습니다. 따라서 앞에서 사용했던 그리디 알고리즘 또한 당연히 활용 불가능합니다. 현재 선택이 이후의 선택에 영향을 미칠 수 있기 때문입니다.

 

아까와 같은 상황에서 이번에는 상자를 열 수 없다고 생각해 봅시다. 상자를 열어 금괴 일부를 가져갈 수 없기 때문에 상자를 가져가거나(1), 가져가지 않는(0) 두 가지 선택지 밖에 없습니다.

이러한 상황에서는 다이나믹 프로그래밍(Dynamic Programming)을 활용하여 문제를 해결해야 합니다. 배낭의 용량과 물품의 가치를 기반으로 최적의 해를 찾습니다.

 

배낭의 남은 용량을 M, 현재 넣으려는 물건의 무게를 N, 현재 넣으려는 물건의 가치를 V일 때, K번 째 물건을 넣으려고 한다고 가정할 경우, 두 가지 상황을 고려해 볼 수 있습니다.

 

1. 넣으려는 K번 째 물건의 무게가 남은 배낭의 용량보다 커서 넣을 수 없을 때

2. 넣으려는 K번 째 물건의 무게가 남은 배낭의 용량보다 작아서 넣을 수 있을 때

 

위의 상황을 도식화해 보면 아래와 같습니다. 

조금 자세히 살펴보면 아래와 같이 기존의 값을 재활용하는 경우가 많은 것을 확인할 수 있습니다. 즉 해당 문제는 다이나믹 프로그래밍으로 해결이 가능한 문제입니다.

용량이 M, 가치가 0인 배낭에서 N개의 물건을 넣으면 용량이 M-N, 가치가 V인 배낭이 되는 것으로 생각하면 쉽습니다.

 

이를 수식으로 작성해 보면

1. 물건의 무게 N > 현재 남은 배낭 용량 M (넣을 수 없을 때)

dp[K][M] = dp[K-1][M]

 

2. 물건의 무게 N <= 현재 남은 배낭 용량 M (넣을 수 있을 때)

dp[K][M] = max(dp[K-1][M], dp[K-1][M-N] + V)

 

이 됩니다.

 

0-1 냅색 문제 코드

# 0-1 Knapsack
def knapsack(weights, values, capacity):
    n = len(weights) # 물품 갯수
    dp = [[0 for _ in range(capacity+1)] for _ in range(n+1)]
    
    for i in range(1, n+1): # 물품 iteration
        for w in range(1, capacity+1): # 무게 1~16
            if weights[i-1] <= w: # 현재 물품 무게가 남은 가방 용량보다 작을 경우
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
            else: # 현재 물품 무게가 남은 가방 용량보다 클 경우
                dp[i][w] = dp[i-1][w]
                
    return dp[n][capacity]

weights = [12, 1, 4, 1, 2] # 물품의 무게 데이터
values = [4, 2, 10, 1, 2] # 물품의 가치 데이터
capacity = 15 # 배낭의 무게 용량
print(knapsack(weights, values, capacity))

 

References

https://namu.wiki/w/%EB%B0%B0%EB%82%AD%20%EB%AC%B8%EC%A0%9C

https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C

https://howudong.tistory.com/106