2021. 7. 13. 17:20ㆍFront-end/알고리즘
오늘은 동적 프로그래밍 문제 중 대표적인 유형인 0/1 배낭 문제에 대해 알아보겠습니다.
물건의 개수 N이 주어지고, 배낭이 최대로 버틸 수 있는 무게 K가 주어지고
각 물건의 무게와 가치가 주어질 때 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하는 문제입니다.
문제가 0/1 배낭 문제라고 불리는 이유는 물건을 쪼개서 넣을 순 없고 물건을 넣거나/안넣거나 둘 중 하나의 선택만 할 수 있기 때문입니다.
예를 들어 물건의 개수가 4개, 배낭의 무게는 7이고 각 물건의 무게와 가치가 다음과 같다고 합시다.
물건의 개수가 4개밖에 되지 않기 때문에 브루트포스(완전탐색)로 구하더라도 짧은 시간내에 금방 구할 수 있으나 물건의 개수가 조금만 늘어나더라도 따져보아야할 경우의 수는 기하급수적으로 늘어나기 때문에 이 문제는 동적 프로그래밍을 통해 구해야 합니다.
우선 값을 저장할 dp를 2차원 배열로 만듭니다.
우리는 dp[i][j] 이런식으로 값을 저장할 것인데, 여기서 i는 물건의 번호, j는 배낭의 용량이 됩니다.
* dp[i][j] : i번째 물건까지 살펴보고 배낭의 용량이 j일 때 배낭에 들어간 물건의 가치합의 최댓값 을 의미합니다.
즉 예를 들어 dp[2][3]은 2번째 물건까지 살펴보았고 배낭의 용량이 3일 때의 경우라고 할 수 있습니다.
그럼 우리가 궁극적으로 구하고자 하는 답은 dp[N][K]에 있을 것입니다.
dp[i][j]가 위의 표로 표현된다고 했을 때, 우선 dp[i][0]과 dp[0][j]은 모두 마진으로 0을 채워줍니다.
(dp[i][0] : 어떤 물건이던 배낭의 무게가 0일 때는 물건이 들어갈 수 없기 떄문
dp[0][j] : 배낭의 무게가 몇이던 물건을 선택하지 않았으므로)
그리고 첫번째 물건은 위와 같이 채울 수 있습니다.
첫번째 물건은 무게가 6이고 가치가 13인데, 배낭의 무게가 5일때까지는 첫번째 물건을 넣을 수 없기 때문에 배낭의 무게가 6일 때와 배낭의 무게가 7일 때 첫번째 물건을 넣을 수 있으므로 가치인 13이 들어가게 됩니다.
여기서부터 정신을 잘 차려야 하는데요.
두번째 물건은 무게가 4, 가치가 8인 물건입니다.
무게가 4이기 때문에 배낭의 무게가 3일때 까지는 들어갈 수 없습니다.
그러므로 이전 물건까지 살펴보았던 dp[i-1][j]의 값을 그대로 가져옵니다. 그러므로 dp[2][1] ~ dp[2][3]에는 0이 채워집니다.
그리고 dp[2][4]에서는 배낭의 무게가 4인데 물건의 무게가 4이니까 두번째 물건을 넣을 수 있죠.
그러면 이전 물건까지 살펴보았던 dp[i-1][j]와 dp[i-1][j - w[j]] + v[i] 중 더 큰 값을 넣는겁니다.
dp[i-1][j]는 dp[1][4] = 0 이고 dp[i-1][j - w[j]] + v[i] = dp[1][0] + v[2] = 0 + 8 = 8이므로 최댓값인 8이 오는 것입니다.
그렇게 가다가 dp[2][6]을 한번 봅시다. 배낭의 무게가 6이므로 두번째 물건을 넣을 수 있습니다.
1. 현재 물건을 포함하지 않는 경우: dp[1][6] = 13
2. 현재 물건을 포함하는 경우 : dp[1][6 - 현재 물건의 무게(4)] + 현재 물건의 가치 (8) = 8
이 중 최댓값이 13이므로 13이 들어가는 것입니다.
이렇게 해서 채워나가다보면 위와 같이 채워집니다.
설명이 장황했지만 결국 포인트는
dp[i][j] : 1. 현재 물건을 포함하지 않는 경우 : 이전에 구한 dp[i-1][j]
2. 현재 물건을 포함하는 경우 : 남은 공간의 가치 ( dp[i-1][j - w[j]] ) + 현재 물건의 가치 ( v[j] )
1번과 2번 중 최댓값이 dp[i][j]가 됩니다.
현재 물건을 포함하는 경우에서 dp[i-1][j-w[j]] + v[j]인 이유는, 우선 dp[i-1][j-w[j]]는 남은 공간의 가치를 말합니다. 즉 현재 물건을 포함했을 경우 i번째 물건을 위해 i번째 물건 만큼의 무게를 비웠을 때의 최대가치는 i-1번째의 j - w[j]에 저장이 되어있기 때문에 그 곳에 가서 보는겁니다. 그리고 현재 물건의 가치를 더해주면 되는 것입니다.