[Python] 배낭문제(0-1 knapsack problem) 알고리즘

- 처음 화면 -

 

---

설계

1. 배낭 문제(Knapsack Problem 냅색 프라블럼)는 조합 최적화의 유명한 문제이다.

간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

 

2. 배낭문제는 짐을 쪼갤 수 있는 경우의 분할가능 배낭문제(Fractional Knapsack Problem)와 짐을 쪼갤 수 없는 경우의0-1 배낭문제(0-1 Knapsack Problem) 두 가지로 나눌 수 있는데, 이번 게시글은 0-1 배낭문제(0-1 Knapsack Problem)을 다뤄보았다.

---

코드

def knapsack(values, weights, capacity):
    n = len(values)
    m = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] > w:
                m[i][w] = m[i - 1][w]
            else:
                m[i][w] = max(m[i - 1][w], m[i - 1][w - weights[i - 1]] + values[i - 1])
    
    max_value = m[n][capacity]
    
    items = []
    w = capacity
    for i in range(n, 0, -1):
        if m[i][w] != m[i - 1][w]:
            items.append(i - 1)
            w -= weights[i - 1]
    
    return max_value, items

values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
max_value, items = knapsack(values, weights, capacity)

print("최대 값어치:", max_value)
print("선택한 물건:", items)

 

 

---

실행

012

- 실행 -

 

---

마무리

배낭문제 중 짐을 쪼갤 수 없는 경우의 0-1 배낭문제(0-1 Knapsack Problem)를 다뤄보았습니다.