이 글에서는 고전적인 조합 최적화 문제인 0-1 배낭 문제(0-1 Knapsack Problem)를 파이썬으로 해결하는 방법을 단계별로 살펴보겠습니다.
문제 정의
n개의 물건이 주어지고, 각 물건마다 무게(weight)와 가치(value)가 정해져 있습니다. 최대 용량이 W인 가방에 이 물건들을 담아야 하며, 목표는 가방에 담을 수 있는 물건들의 총 가치를 최대화하는 것입니다. 단, 각 물건은 한 번만 담을 수 있으며(0-1 제약), 가방의 용량을 초과할 수 없습니다.
그럼 두 가지 접근법을 통해 해결 과정을 살펴보겠습니다.
1. 브루트 포스(Brute-force) 접근법
가장 직관적인 방법은 모든 경우의 수를 탐색하는 것입니다. 각 물건에 대해 '담는다' 또는 '담지 않는다'라는 두 가지 선택지를 재귀적으로 검토하며 최대 가치를 찾습니다.
예제 코드
#가방에 저장할 수 있는 최대 가치를 반환합니다
def knapSack(W, wt, val, n):
# 초기 조건
if n == 0 or W == 0 :
return 0
# 물건의 무게가 남은 용량보다 크면 포함하지 않습니다
if (wt[n-1] > W):
return knapSack(W, wt, val, n-1)
# n번째 물건을 포함하는 경우와 제외하는 경우 중 더 큰 값을 반환합니다
else:
return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
knapSack(W, wt, val, n-1))
# 위 함수 테스트
val = [50,100,150,200]
wt = [8,16,32,40]
W = 64
n = len(val)
print (knapSack(W, wt, val, n))
실행 결과
350
이 방식은 시간 복잡도가 O(2ⁿ)로, 물건의 개수가 늘어날수록 연산량이 지수적으로 증가한다는 단점이 있습니다.
2. 동적 계획법(Dynamic Programming) 접근법
브루트 포스 방식은 같은 하위 문제를 반복해서 계산하므로 비효율적입니다. 동적 계획법을 활용하면 이미 계산한 결과를 2차원 표(K)에 저장하고, 바텀업(bottom-up) 방식으로 표를 채워 나가며 중복 계산을 제거할 수 있습니다.
예제 코드
# 동적 계획법 접근
# 가방에 저장할 수 있는 최대 가치를 반환합니다
def knapSack(W, wt, val, n):
K = [[0 for x in range(W + 1)] for x in range(n + 1)]
# 바텀업 방식으로 테이블을 채웁니다
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
K[i][w] = 0
elif wt[i-1] <= w:
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
else:
K[i][w] = K[i-1][w]
return K[n][W]
# 메인
val = [50,100,150,200]
wt = [8,16,32,40]
W = 64
n = len(val)
print(knapSack(W, wt, val, n))
실행 결과
350
여기서 K[i][w]는 'i번째 물건까지 고려했을 때, 용량 w로 얻을 수 있는 최대 가치'를 의미합니다. 모든 변수는 지역 범위(local scope) 내에서 선언되며, 위 그림에서 각 변수의 참조 관계를 확인할 수 있습니다.
동적 계획법의 시간 복잡도는 O(n × W)로, 브루트 포스 방식보다 훨씬 효율적입니다.
결론
이 글에서는 0-1 배낭 문제를 파이썬으로 해결하는 두 가지 방법, 즉 재귀 기반의 브루트 포스 접근법과 동적 계획법을 살펴보았습니다. 입력 크기가 작다면 브루트 포스로도 충분하지만, 성능이 중요한 환경에서는 중복 계산을 제거하는 동적 계획법을 활용하는 것이 바람직합니다.