배낭 문제는 정해진 비용 내에서 최적의 가치를 갖는 해를 찾는 문제다. 처음 이 문제를 접하는 사람들 대부분이 그리디로 접근하지만 그리디 알고리즘만으로는 해결할 수 없는 배낭 문제도 있다. 배낭 문제는 크게 두 유형으로 분류되는데 먼저 그리디 알고리즘을 적용할 수 있는 분할 가능한 배낭 문제와 그리디 알고리즘으로는 해결하기 어려운 0-1 배낭 문제가 있다.
1. 분할 가능한 배낭 문제
분할 가능한 배낭 문제는 말 그대로 가치와 비용을 분할해 가져올 수 있다.
예를 들어 10kg의 제한을 두고 배낭을 싸는데 5kg에 75의 가치를 가진 A와 4kg에 120의 가치를 가진 B, 7kg에 140의 가치를 가진 C가 있다고 해보자. 여기서 A, B, C 모두 원하는 만큼 쪼개서 가져갈 수 있는 물건이라고 가정하면 1kg당 가장 높은 가치를 가진 B를 4kg 챙기고 그 다음으로 가치가 높은 C를 6kg 챙겨가는 것이 총 240의 가치를 가지므로 정답이다.
이런 문제는 단위 비용 당 가치를 계산해 가치가 높은 것을 우선적으로 선택하는 그리디 알고리즘이 적용 가능하다.
2. 0-1 배낭 문제(분할 불가능한 배낭 문제)
위 문제의 예시를 다시 보자. 이번에는 A, B, C 모두 분할 할 수 없는 물체라고 가정하자. 그렇다면 B를 담고 다음으로 가치가 높은 C를 담을 수 없으므로 A를 담는 것이 총 195의 가치를 갖는 정답이 된다. 만약 여기에 3kg에 75의 가치를 가진 D가 더해진다면 어떨까.
가장 높은 가치를 갖는 B를 먼저 담고 그다음으로 가치가 높은 D를 담으면 195의 가치를 갖는다. 하지만 C와 D를 담으면 215로 최적해를 얻을 수 있다.
이렇게 단순히 단위 비용 당 가치로 계산할 수 없어지며 복잡하고 정교하게 그리디 알고리즘을 만든다해도 모든 상황에 최적해를 찾을 수 없게 된다. 따라서 0-1 배낭 문제는 다른 방법으로 해결해야 한다.
2-1. 문제 해결
문제 상황을 하위 단계로 나누어 상위 문제를 해결할 수 있는지 확인해보자. 물건에 번호를 매겨서 총 n개의 물건 중 i번째 물건까지만 사용해 최적해를 찾는다면 i번째 물건을 선택하는 경우와 선택하지 않는 경우로 나뉜다. 둘 중 더 가치가 높은 것이 최적해다. 제한 비용도 바꿀 수 있다고 해보자. 그렇다면 i번째 물건까지만을 사용해 w의 비용으로 최고의 가치를 얻는 방법은 i번째 물건 없이 i-1번째까지의 물건만으로 얻은 최적해이거나(한 단계 하위 문제의 해이므로 이미 앞서 구했을 것이다.), i-1번째까지의 물건으로 구하고자 하는 제한 비용 w에서 i번째 물건의 비용인 wi를 제외한(배낭으로 치면 i번째 물건을 담기 위한 공간을 남겨둔 상태라고 생각할 수 있겠다.) w-wi 비용 안에서 얻을 수 있는 최적해일 것이다. 정리하면 아래와 같다.
그렇다면 이 문제는 하위 문제의 해가 상위 문제의 해를 구성할 수 있으므로 다이나믹 프로그래밍으로 해결할 수 있다.
문제에서 구하고자 하는 최대 비용이 K, 전체 물건의 갯수가 N이라고 하고 이를 N의 길이를 갖는 2차원 배열 item으로 만들어 비용 weight와 가치 value를 저장한다고 하면, i번째 물건으로 k의 비용 안에서 얻는 최적해를 구하는 점화식을 아래와 같이 표현해볼 수 있다.
2-2. 소스코드
코드로 구현한 것은 아래와 같다. for문의 반복 범위가 1부터 N + 1, K + 1까지인 이유는 i - 1을 참조하는 과정에서 index out of range 예외를 피하기 위해서이다.
for i in range(1, N + 1):
for j in range(1, K + 1):
weight = item[i][0]
value = item[i][1]
if j >= weight
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value)
else:
dp[i][j] = dp[i - 1][j]
2-3. 연습문제
1535번: 안녕
첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번
www.acmicpc.net
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
1106번: 호텔
첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때
www.acmicpc.net
1106번: 호텔 문제는 각 물건을 여러 번 사용할 수 있다는 점에서 생각할 것이 한 가지 더 있다.
