파이썬으로 푸는 0/1 배낭 문제: 용량 제한 안에서 얻을 수 있는 최대 가치 찾기

문제 이해하기

이번 글에서는 대표적인 동적 계획법(DP) 문제인 0/1 배낭 문제(Knapsack Problem)를 파이썬으로 해결하는 방법을 살펴보겠습니다.

길이가 같은 두 개의 리스트 weights와 values, 그리고 하나의 숫자 capacity(용량)가 주어진다고 가정해 봅시다. 여기서 weights[i]와 values[i]는 각각 i번째 아이템의 무게와 가치를 나타냅니다.

목표는 다음과 같습니다:

담은 아이템들의 총 무게가 capacity를 초과하지 않아야 합니다.
각 아이템은 최대 한 번만 선택할 수 있습니다.
위 조건을 만족하면서 얻을 수 있는 최대 가치를 구합니다.

예를 들어 입력이 다음과 같다면,

weights = [2, 3, 4]
values = [2, 6, 4]
capacity = 6

출력은 8이 됩니다. 무게 3짜리 아이템(가치 6)과 무게 2짜리 아이템(가치 2)을 함께 담으면 총 무게 5로 가치 8을 얻을 수 있고, 이것이 가능한 조합 중 가장 큰 값이기 때문입니다.

접근 방법: 동적 계획법(Dynamic Programming)

핵심 아이디어는 dp[i][j]를 "처음 i개의 아이템만 고려했을 때, 용량 j 안에서 얻을 수 있는 최대 가치"로 정의하는 것입니다. 각 아이템마다 두 가지 선택지가 있습니다.

담지 않는 경우: dp[i-1][j]
담는 경우(무게가 허용될 때): dp[i-1][j - weights[i-1]] + values[i-1]

두 값 중 더 큰 것을 선택하면 됩니다.

알고리즘 단계

n := weights의 크기로 설정합니다.
(n+1) × (capacity+1) 크기의 dp 테이블을 만들고 0으로 초기화합니다.
i를 0부터 n까지 반복하면서, j를 0부터 capacity까지 반복합니다.
- i가 0이거나 j가 0이면 → dp[i][j] = 0
- 그렇지 않고 weights[i-1] <= j이면 → dp[i][j] = max(dp[i-1][j-weights[i-1]] + values[i-1], dp[i-1][j])
- 그 외의 경우 → dp[i][j] = dp[i-1][j]
최종적으로 dp[n][capacity]를 반환합니다.

파이썬 구현 코드

class Solution:
   def solve(self, weights, values, capacity):
      n = len(weights)
      dp = [[0 for i in range(capacity+1)] for _ in range(n+1)]
      for i in range(n+1):
         for j in range(capacity+1):
            if i == 0 or j == 0:
               dp[i][j] = 0
            elif weights[i-1] <= j:
               dp[i][j] = max(dp[i-1][j-weights[i-1]] + values[i-1], dp[i-1][j])
            else:
               dp[i][j] = dp[i-1][j]
      return dp[n][capacity]

ob = Solution()
weights = [2, 3, 4]
values = [2, 6, 4]
capacity = 6
print(ob.solve(weights, values, capacity))

입력

[2, 3, 4], [2, 6, 4], 6

출력

복잡도 분석

이 알고리즘의 시간 복잡도는 O(n × capacity)이며, 공간 복잡도 역시 O(n × capacity)입니다. 여기서 n은 아이템의 개수입니다. 참고로 dp 배열을 1차원으로 압축하면 공간 복잡도를 O(capacity)까지 줄일 수 있으므로, 메모리가 중요한 상황에서는 최적화를 고려해 볼 만합니다.