0-1 배낭 문제
분할 가능 배낭 문제와 달리 짐을 쪼갤 수 없는 0-1 배낭 문제를 풀이해 보자. 이 문제는 '탐욕 선택 속성'이 있는 문제가 아니며 '중복된 하위 문제들' 속성을 갖고 있으므로 다이나믹 프로그래밍으로는 풀 수 있다.
단가 순으로 그리디하게 배치해서 풀이했던 분할 가능 배낭 문제와 달리, 0-1 배낭 문제는 짐을 쪼갤 수 없다. 이 경우 모든 경우의 수를 계산해야 한다. 먼저, 입력값으로 짐을 정의하고 zero_one_knapsack() 풀이 함수를 호출한다.
cargo = [
(4, 12),
(2, 1),
(10, 4),
(1, 1),
(2, 2),
]
print(zero_one_knapsack(cargo))zero_one_knapsack() 함수는 다음과 같이 정의한다.
def zero_one_knapsack(cargo):
capacity = 15
pack = []
...pack이라는 리스트 변수에 6X16 행렬 형태의 중간 결과 테이블이 생성될 것이다. 즉 이 테이블을 글자 그대로 타뷸레이션하는 다이나믹 프로그래밍 풀이가 될 것이다. 테이블 크기의 기준은 짐의 최대 개수 +1, 배낭의 최대 용량 +1 이렇게 6x16이며, 이 테이블 각각의 셀에는 그 위치까지의 짐의 개수와 배낭의 용량에 따른 최댓값이 담기게 된다. 전체 코드는 다음과 같다.
def zero_one_knapsack(cargo):
capacity = 15
pack = []
for i in range(len(cargo) + 1):
pack.append([])
for c in range(capacity + 1):
# fixme 가로와 세로의 첫줄을 다 0으로 채움.
if i == 0 or c == 0:
pack[i].append(0)
# fixme 짐 개수가 1개 이상이고, 배낭 용량도 1개 이상일 때
# fixme i는 1부터 시작하므로 cargo에서 처음부터 확인하려면 cargo[i-1][1]으로 kg을 가지고 와서
# fixme 현재 capacity보다 작거나 같을 때 가방에 넣을지 말지 결정한다.
elif cargo[i - 1][1] <= c:
pack[i].append(
max(
# fixme cargo에서 달러 +
# fixme 짐의 개수가 하나 전일 때(i-1),
# fixme 현재 capacity c 에서 지금 들어가려는 짐의 capacity인 cargo[i-1][1]를 뺀 capacity 부분의 가치를 확인해서 둘이 더함.
cargo[i - 1][0] + pack[i - 1][c - cargo[i - 1][1]],
# fixme 전의 값과 비교해서 더 큰 값을 선택
pack[i - 1][c]
))
else:
# fixme. 아니면 전꺼 그대로 추가
pack[i].append(pack[i - 1][c])
return pack[-1][-1]
cargo = [
(4, 12),
(2, 1),
(10, 4),
(1, 1),
(2, 2),
]
print(zero_one_knapsack(cargo))이 코드의 실행 결과로 pack에는 행렬 형태의 밑의 표가 생성된다.
이 표에서 세로 축은 짐의 개수, 가로축은 배낭의 용량이다. 각각의 셀은 그 위치까지의 짐의 개수와 배낭의 용량에 따른 최댓값이다. 즉 짐이 4개가 있을 때는 차례대로 ($3, 12kg), ($2, 1kg), ($10, 4kg), ($1, 1kg)일 것이고, 배낭의 용량이 4라면 4kg인 $10짜리 짐 하나를 담는게 가장 이익이다. 따라서, 4x4 위치의 최댓값은 10이며 위의 표에서도 10인 것을 확인할 수 있다. 배낭의 용량이 5라면 1kg인 $2를 추가해 12가 될 수 있다. 마찬가지로 이 표에서도 12다. 이렇게 가장 마지막 위치인 5x15까지 이동한 총 5개의 짐, 용량이 15인 배낭의 최댓값은 15이며, 이 문제의 정답은 15임을 확인할 수 있다. 이렇게 최악의 경우 O(2^n)의 계산이 필요한 0-1 배낭 문제를 여기서는 타뷸레이션 방식으로 O(nW)(n: 짐의 개수, W: 배낭의 용량)으로 풀 수 있다.
최댓값을 추출하는 부분이 헷갈려 주석에 적어놨다.
출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]