문제 : http://codeup.kr/JudgeOnline/problem.php?id=3740
다이나믹 프로그래밍 DP의 대표 문제 중 하나인 물건을 넣느냐 빼느냐를 선택하는 0/1 배낭문제.
물건의 개수가 N이고 배낭에 담을 수 있는 최대 무게가 W이다.
물건은 종류별로 1개씩 있다.
d[i][j] = 물건을 i번째 까지 배낭에 넣는다고 가정했을 때, 무게 j를 초과하지 않으면서 배낭에 넣을 수 있는 물건들의 가격의 총합의 최대값
d[i][j] = d[i - 1][j] (j < w[i] 인 경우, i번째 물건을 못 넣는 경우, 변함 없으므로 d[i-1][j])
d[i][j] = max(d[i - 1][j], d[i - 1][j - w[i]] + v[i]); ( j >= w[i]인 경우, i번째 물건을 넣을 수 있는 경우)
d[i - 1][j - w[i]] : i-1번째 물건을 이용, j - w[i]의 무게로 배낭을 쌀 수 있는 가격의 최대 값
v[i] : i번째 물건을 넣을 때 추가되는 물건의 가격
j에서 w[i]를 빼는 이유는 i번째 물건을 넣어야 하는데 j무게를 넘기면 안되니까 배낭에 w[i]가 들어갈 공간을 만들어 줘야 한다. 따라서 d[i-1][j-w[i]](무게 j - w[i]를 초과하지 않으면서 배낭에 넣을 수 있는 물건의 가격 총합)에 v[i]를 더한 것이 i번째 물건을 넣을 때 최대 가격이 된다.
d[i - 1][j - w[i]] + v[i] : 배낭에 j 무게를 채울 때 i번째 물건을 넣는 경우 가격의 총합의 최대값
d[i - 1][j] : 배낭에 j 무게를 채울 때 i번째 물건을 넣지 않을 때 가격의 총합의 최대값
따라서, d[i][j] = max(i번째 물건을 넣지 않을 때(0) 가격 최대, i번째 물건을 넣을 때(1) 가격 최대) 가 된다. 그래서 01 배낭문제라고 한다.
[그림 1]은 문제의 예시를 위의 점화식을 이용해서 배열을 채웠을 때 모습이다.
예를 들어 d[3][5]를 채운다고 할 때,
d[i - 1][j - w[i]]는 3이 되고 v[i]는 3이여서 3번째 물건을 배낭에 넣을 때 가능한 최대 가격은 6이다.
d[i - 1][j]는 5이므로
6과 5 중 최대 값인 6이 d[3][5]에 들어가게 된다.
공간 복잡도는 d 배열의 크기가 물건 개수(N) * 배낭에 넣을 수 있는 최대 무게 (W) 이므로 O(NW)이다. 사실 d배열을 채울 때 점화식을 보면 현재 행의 바로 위의 행의 정보만으로 채우기 때문에 2행만 사용해도 문제를 풀 수 있다. d[2][W]을 만들어서 문제를 풀 경우 공간 복잡도를 O(W)으로 줄일 수 있다.
시간 복잡도는 d[i][j]를 채울 때 d[i-1][j]와 d[i-1][j-w[i]] + v[i] 이렇게 2개만 비교하므로 O(1)이 소요된다. 이를 d배열의 모든 칸을 채울 때 실행하므로 O(NW) * O(1). 따라서 O(NW)이 된다.
소스 코드
공간복잡도 O(NW) :https://gist.github.com/fpdjsns/021c88e674f2ad4d8c623990f08693e2
공간복잡도 O(2*W): https://gist.github.com/fpdjsns/9b4d552730dcb03898426c36a6395412
정올 배낭채우기2(1278) : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=561&sca=3050
여기도 말만 달라졌을 뿐 문제랑 입출력 똑같다.
배낭 문제는 01 Knapsack 뿐만아니라 물건을 쪼갤 수 있는 부분 배낭 문제, fractional knapsack 가 있다.
이는 그리디 방법으로 푼다. 비교적 01 Knapsack 보다는 쉽다.
해당 문제를 찾으면 다른 포스팅에서 설명하겠습니다.
댓글